[CF808D] Array Division（暴力，枚举）

题目链接：http://codeforces.com/contest/808/problem/D

题意：给n个数，现在允许一个数交换到另外一个地方。希望这n个数分成两部分的和相等，问这个数列满足不满足条件。

可以认为两个部分是两个集合，那么从左到右地扫，每扫到一个值认为这个值为一个pivot，那么就把这个值放到另外一个集合中，并且从当前集合中去掉这个值，看看和是不是相等。这个值在初始时可以属于左也可以属于右，因此要枚举两次。

一开始认为这个pivot只存在于中间，即恰好满足s[pivot]>avg或者s[pivot]<avg的地方，但是后来被cha了。。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 200200;
 6 int n;
 7 LL a[maxn], s[maxn];
 8 LL tot;
 9 
10 int main() {
11     // freopen("in", "r", stdin);
12     while(~scanf("%d",&n)) {
13         tot = 0;
14         memset(s, 0, sizeof(s));
15         for(int i = 1; i <= n; i++) {
16             scanf("%I64d", &a[i]);
17             tot += a[i];
18         }
19         if(tot & 1) {
20             puts("NO");
21             continue;
22         }
23         bool exflag = 0;
24         tot >>= 1;
25         LL lo = 0;
26         int pos = -1;
27         for(int i = 1; i <= n; i++) {
28             if(lo + a[i] > tot) {
29                 pos = i;
30                 break;
31             }
32             lo += a[i];
33         }
34         LL hi = tot * 2 - lo;
35         // cout << lo << " " << hi << endl;
36         for(int i = pos; i <= n; i++) {
37             if(lo + a[i] == hi - a[i]) {
38                 exflag = 1;
39                 break;
40             }
41         }
42         lo += a[pos]; hi -= a[pos]; pos--;
43         // cout << lo << " " << hi << endl;
44         for(int i = 1; i <= pos; i++) {
45             if(lo - a[i] == hi + a[i]) {
46                 exflag = 1;
47                 break;
48             }
49         }
50         if(exflag) puts("YES");
51         else puts("NO");
52     }
53     return 0;
54 }

被cha代码

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 200200;
 6 int n;
 7 LL a[maxn], s[maxn];
 8 LL tot;
 9 map<LL, LL> vis;
10 
11 int main() {
12     // freopen("in", "r", stdin);
13     while(~scanf("%d",&n)) {
14         tot = 0;
15         memset(s, 0, sizeof(s));
16         for(int i = 1; i <= n; i++) {
17             scanf("%I64d", &a[i]);
18             tot += a[i];
19             s[i] = s[i-1] + a[i];
20         }
21         if(tot & 1) {
22             puts("NO");
23             continue;
24         }
25         bool exflag = 0;
26         vis.clear();
27         for(int i = 1; i <= n; i++) {
28             if(s[i] == s[n]-s[i]) {
29                 exflag = 1;
30                 break;
31             }
32             if(vis[2*a[i]] >= 1) {
33                 exflag = 1;
34                 break;
35             }
36             LL tmp = tot - 2 * s[i];
37             if(tmp == 0) {
38                 exflag = 1;
39                 break;
40             }
41             if(tmp >= 0) vis[tmp]++;
42         }
43         vis.clear();
44         for(int i = n; i >= 1; i--) {
45             if(s[i] == s[n]-s[i]) {
46                 exflag = 1;
47                 break;
48             }
49             if(vis[2*a[i]] >= 1) {
50                 exflag = 1;
51                 break;
52             }
53             LL tmp = 2 * s[i] - tot;
54             if(tmp == 0) {
55                 exflag = 1;
56                 break;
57             }
58             if(tmp >= 0) vis[tmp]++;
59         }
60         if(exflag) puts("YES");
61         else puts("NO");
62     }
63     return 0;
64 }