题目大意
ZY一向热衷于出一些水题，例如“两个数列”。但是ZY却因为这道题被同学们狠狠的骂了一顿。委屈的ZY决定再出一道水题，以证明他是个菜鸡。
ZY有一个长度为$2n$的整数数列，每一项的绝对值$\left|a_i\right|\le n$，且满足所有数的和$a_1+a_2+a_3+\cdots+a_{2n}=1$。现在ZY想知道是否能从中取出若干个数，使得它们的和等于$0$。然后，ZY就被难住了，这个问题就交给你来解决了。
题目分析
考场居然骗了$80$分，有搞头有搞头。
搜索好像能拿$70$分。
输出$-1$可以拿$0$分（原因参考证明部分）。
挺不错的一道思维题，据说是从自招题改编的。
题目的每一个条件都是有用的。
考虑，若原数列存在$0$或$1$，直接输出$0$或除了$1$剩下的数即可，否则：
- 随便选一个数放进数组。
- 若当前所选数之和为$0$或$1$，找到答案。
- 若当前所选数之和$\lt0$，选一个正数加入数组。
- 若当前所选数之和$\gt1$，选一个负数加入数组。
- 在Hash表中查询当前所选数和是否出现过，若出现过则找到答案。
- 将当前所选数和加入Hash表，返回第$2$步。
时间复杂度$O(n)$。
至于证明：
若始终没有出现答案，则当前数之和$\in[-n,0)\bigcup(1,n]$。
而这样的数只有$2n-1$个，而总共有$2n$个数。
根据抽屉原理，必定有两个数相同，因此用这个方法一定能够找到答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,posi[maxn],nega[maxn],pos_posi,pos_nega,cnt_posi,cnt_nega,sum=0,M1[maxn<<1],M2[maxn<<1];
int main() {
n=Get_Int()<<1;
for(int i=1; i<=n; i++) {
int x=Get_Int();
if(x==0) {
puts("1\n0");
return 0;
}
if(x>0)posi[++cnt_posi]=x;
else nega[++cnt_nega]=x;
}
sum+=posi[++pos_posi];
while(true) {
if(sum<0)sum+=posi[++pos_posi];
if(sum>1)sum+=nega[++pos_nega];
if(sum==0) {
printf("%d\n",pos_posi+pos_nega);
for(int i=1; i<=pos_posi; i++)printf("%d ",posi[i]);
for(int i=1; i<=pos_nega; i++)printf("%d ",nega[i]);
return 0;
}
if(sum==1) {
printf("%d\n",cnt_posi+cnt_nega-pos_posi-pos_nega);
for(int i=pos_posi+1; i<=cnt_posi; i++)printf("%d ",posi[i]);
for(int i=pos_nega+1; i<=cnt_nega; i++)printf("%d ",nega[i]);
return 0;
}
if(M1[sum+n]) {
printf("%d\n",pos_posi+pos_nega-M1[sum+n]-M2[sum+n]);
for(int i=M1[sum+n]+1; i<=pos_posi; i++)printf("%d ",posi[i]);
for(int i=M2[sum+n]+1; i<=pos_nega; i++)printf("%d ",nega[i]);
return 0;
}
M1[sum+n]=pos_posi,M2[sum+n]=pos_nega;
}
return 0;
}
|
