输入数组长度n,问是否存在这样的一个数组:1. 数组前一半均为偶数,后一半均为奇数;2.前一半和后一半数组中元素的和相等
? 做的时候读题太粗心,只看到了最大和。WA了之后读了好几次题也没看到最长这个优先级最高的条件,一直在错误的地方修改......
题目中会输入一组长为n的数组,要求输出一个最长的交错子序列[1]的最大和
贪心:遍历数组,每个连续的同号子串取最值。
cin >> t;
while(t--){
cin >> n;
ans = mx = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
if(!i || a[i] * a[i - 1] < 0){
ans += mx;
mx = a[i];
}else{
mx = max(mx,a[i]);
}
}
cout << ans + mx << endl;
}
输入由n个整数组成的数组a,和整数k,替换数组中de一些元素为[1,k]中的任一元素,使数组满足:
对于确定的x,每对元素的交换次数确定
a + b = x
x ∈[min(a,b) + 1,max(a,b) + k + 1),半开半闭的区间方便合并,获得最小和,最大和,差分,此区间 + 1--起始位置 + 2,左边界(闭)-1,右边界(开) +1
其它
交换次数存在一个最大值,当x = k + 1,为 n / 2(所有元素值的区间[1,k]);对每一对元素,计算交换次数为1的区间,使用差分思想通过cnt数组在区间外+2,区间内+1,对每一对元素的和特殊处理;在枚举完所有的元素对后,将差分数组cnt修改为前缀和即为相应x的替换次数,ans 初始化为n / 2,遍历cnt数组寻找最小替换次数。。。
const int kN = 2e5 + 10,kM = 4e5 + 5;
int t,n,k,l,r,ans,a[kN],cnt[kM];
//替换最少数量的元素,数组中对称元素和满足 a[i] + a[n - i + 1] = x;x为某个定值
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >>t;
while(t--){
memset(cnt,0,sizeof(cnt));
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n / 2; i++){
l = min(a[i],a[n - i + 1]) + 1;
r = max(a[i],a[n - i + 1]) + k + 1;
cnt[1] += 2;//差分 边界[2,l) 需要两次
cnt[l]--;//[l,r] 一次
cnt[r]++;
cnt[a[i] + a[n - i + 1]]--;//0
cnt[a[i] + a[n - i + 1] + 1]++;
}
for(int i = 2; i <= 2 * k; i++) cnt[i] += cnt[i - 1];//前缀和
ans = n / 2;
for(int i = 1; i <= 2 * k; i++) ans = min(ans,cnt[i]);
cout << ans << endl;
}
return 0;
}
正负交替 ??
原文:https://www.cnblogs.com/honey-cat/p/12802986.html