广安门外网站建设,ccie网络培训,邢台做移动网站,成都有名的建筑公司有哪些挺好的一道思维题。 分析
因为是对区间修改#xff0c;多次修改肯定会超时#xff0c;很容易想到差分。
那么原题的对区间修改就可以转换为下面三个操作#xff08;均在差分数组中#xff09;#xff1a;
1. 任选一个数1
2. 任选一个数-1
3. 任选两个数1和-1 进一步考… 挺好的一道思维题。 分析
因为是对区间修改多次修改肯定会超时很容易想到差分。
那么原题的对区间修改就可以转换为下面三个操作均在差分数组中
1. 任选一个数1
2. 任选一个数-1
3. 任选两个数1和-1 进一步考虑题目的问题让原数组一样那么就是
a[1]的值任意a[2]开始后面的值均为0。 再分析现有的三个操作最多的操作数肯定是总正数之和或者总负数之和取大的那个
显而易见的因为只能选一个数进行操作。 那么我们再考虑满足当前最少操作数的时候能出现不同序列的数量即a[1]的取值能有多少。
如果正数比负数多那么正数执行操作3减少到0额外的还能执行加法加到a[1]身上也可以不加即选操作2。那么不同的数量就是正数比负数多的部分再1可以一个都不加。
反之负数也是如此但是需要注意负数执行加那么a[1]就是减不能小于0。
正负一样多那肯定就只有一种序列了因为要求操作数最少。 AC代码
#include bits/stdc.h
#define int long long
#define endl \n
using namespace std;const int N1e55;
int n,a[N],pos,neg;void solve(){cinn;for(int i1,t;in;i){cint;a[i]t;a[i1]-t;}for(int i2;in;i)if(a[i]0)neg-a[i];else posa[i];coutmax(pos,neg)endl;//最少操作次数if(posneg){//正数多coutpos-neg1endl;}else if(posneg){cout1endl;}else if(posneg){//负数多if(neg-posa[1])coutneg-pos1endl;else couta[1]1endl;}
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t1;while(t--)solve();return 0;
}
