cf round448

cf round448

A

题目要求

模型转换为n个数字 要成分成2份 求2份的差值最小 输出差值

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define maxn 800
using namespace std;
int n;
int a[maxn];
int main(){
// freopen("input.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) a[i+n]=a[i];
int ans=360;
for(int i=1;i<=n;i++){
int tmp=0;
for(int j=i;j<=2*n;j++){
if(j-i==n) break;
tmp+=a[j];
ans=min(ans,abs(360-2*tmp));
}
}
printf("%d\n",ans);
return 0;
}

思路

数组扩大2倍 每次遍历长度为n的窗口 相当于考虑了每种情况
对于每个窗口 tmp累加前缀和 sum-2×tmp 就是当前状态的答案 维护最小值
这里的sum=360 减去两倍的tmp是因为从一边移动到另一边 实际的贡献为2×tmp

文章目录
  1. 1. cf round448
    1. 1.1. A
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
|