深圳房地产论坛家在深圳,搜索引擎优化行业,中国建设机械教育协会网站,视频网站管理系统cf1453B. Suffix Operations
题意#xff1a;
给你一个整数序列#xff0c;其中有n个元素。你需要对这个序列进行操作。
1 在所有操作开始前#xff0c;你可以选择一个数#xff0c;并修改他的值#xff0c;这个值你可以自己定。本操作无花费。
2 选择一个下标i#…cf1453B. Suffix Operations
题意
给你一个整数序列其中有n个元素。你需要对这个序列进行操作。
1 在所有操作开始前你可以选择一个数并修改他的值这个值你可以自己定。本操作无花费。
2 选择一个下标i将所有下标不小于i的元素加上一个整数x,x可以你自己定。这次操作花费为x的绝对值。
本题给你一个序列要你求要将这个序列中的元素统一至少花费多少。
题解
因为修改只有一次我们先不考虑如果没有修改的话答案就是所有相邻两数差的绝对值之和。 为什么我们的操作是将的下标大于等于i的都x我们考虑差值发现只有第i-1位和第i位的差值发生了改变其他相邻数都没有改变。也就是说我们一次操作其实只能改变这两个相邻数之间的差值那总修改数不就是所有相邻两个数差的绝对值的和.(个人理解) 现在我们有修改操作因为可以随便修改那我们可以将第x位直接修改到我们想要的理想状态那原来的∣ax−1−ax∣∣ax−ax1∣|a_{x-1}-a_{x}||a_{x}-a_{x1}|∣ax−1−ax∣∣ax−ax1∣变成∣ax−1−ax1∣|a_{x-1}-a_{x1}|∣ax−1−ax1∣记得将边界特判一下
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn2e59;
int a[maxn];
int b[maxn];
int main()
{//rd_test();int t;read(t);while(t--){int n;read(n);for(int i1;in;i)read(a[i]);for(int i2;in;i)b[i]abs(a[i]-a[i-1]);ll ans0;for(int i2;in;i)ansb[i];ll sumans;for(int i2;in;i){ansmin(ans,sum-b[i]-b[i1]abs(a[i1]-a[i-1]));}ansmin(ans,min(sum-b[2],sum-b[n]));coutansendl;} //Time_test();
}
