赛时竟然想了好久,后来开窍了,O(n)O(n)O(n) 的做法,dalao 勿喷。
分 222 种情况:翻转 111 次的和没翻转的(如果翻 222 次就没意义了)
每次操作可以给任意一朵花加上或减去任意的美丽程度,所以一朵花只调整一次即可,否则就浪费次数了。
也就是说,遍历两个序列时,如果对应值不同,操作总数 +1+ 1+1。
即翻转后当做没翻转的情况来计算次数,最后再 +1+ 1+1。
#include <iostream> #include <algorithm> using namespace std; int n; int a[500005], b[500005]; void reverseA()//将a序列倒过来 { for (int i = 1, j = n; i < j; i++, j--) swap(a[i], a[j]); } int cal()//计算现在的序列只加减美丽程度,需要操作多少次 { int cnt = 0; for (int i = 1; i <= n; i++) cnt += (a[i] != b[i]);//如果两个不一样,即++ /* 也可改为: if (a[i] != b[i]) cnt++; */ return cnt; } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; int ans = cal();//不翻转的情况 reverseA();//如果翻转 ans = min(ans, cal() + 1);//和翻转的情况取最小即可,记得+1 cout << ans << endl; return 0; }
提交评论