这道题:csp-j2021 小熊的果篮
这是我的代码:
#include <bits/stdc++.h>
using namespace std;
int n;
set<int> s1, s2;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
if (x)
s1.insert(i);
else
s2.insert(i);
}
int now = 0;
bool p = *s1.begin() >= *s2.begin();
while ((!p && !s1.empty()) || (p && !s2.empty())) {
if (!p) {
auto it = s1.upper_bound(now);
if (it == s1.end()) {
now = 0;
p = *s1.begin() >= *s2.begin();
printf("\n");
continue;
}
now = *it;
printf("%d ", now);
s1.erase(it);
p ^= 1;
}
else {
auto it = s2.upper_bound(now);
if (it == s2.end()) {
now = 0;
p = *s1.begin() >= *s2.begin();
printf("\n");
continue;
}
now = *it;
printf("%d ", now);
s2.erase(it);
p ^= 1;
}
}
while (!s1.empty()) {
printf("%d\n", *s1.begin());
s1.erase(s1.begin());
}
while (!s2.empty()) {
printf("%d\n", *s2.begin());
s2.erase(s2.begin());
}
}
这是某个题解的代码:
#include<bits/stdc++.h>
#define INF 200010
using namespace std;
int n;
set<int>s1,s2;//把下标扔在两个set里
int main()
{
scanf("%d",&n);
s1.clear();
s2.clear();
int q;
for(int i=1;i<=n;++i)
{
scanf("%d",&q);
if (q) s1.insert(i);
else s2.insert(i);
}
s1.insert(INF);//这里塞INF的原因是防止set空后的出错
s2.insert(INF);
int nw=0;
bool p=*s1.begin()<*s2.begin()?0:1;//这里是找两种东西最小下标的小值,p是当前删的东西
while(!p && s1.size()>1 || p && s2.size()>1)//因为有个INF,所以size要>1
if (!p)
{
nw=*s1.upper_bound(nw);//upper_bound找下一个
if (nw==INF)//找不完了就从头开始
{
nw=0;
p=*s1.begin()<*s2.begin()?0:1;//p要重新选
puts("");
continue;
}
printf("%d ",nw);//取了,输出,删除
s1.erase(nw);
p=!p;//取另外一坨
}
else//同上
{
nw=*s2.upper_bound(nw);
if (nw==INF)
{
nw=0;
p=*s1.begin()<*s2.begin()?0:1;
puts("");
continue;
}
printf("%d ",nw);
s2.erase(nw);
p=!p;
}
puts("");//最后一个果篮是没换行的
while(s1.size()>1) printf("%d\n",*s1.begin()),s1.erase(*s1.begin());//一坨取完以后,另外一堆是一个区间,一行一行输出
while(s2.size()>1) printf("%d\n",*s2.begin()),s2.erase(*s2.begin());//同上
return 0;
}
我们的思路都一样的,但它的代码过了,但我没过。本来以为我实现出问题了,结果我下载数据后发现,我和题解代码的输出时一样的,但我WA了,为啥???
数据:
100
0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0
题解的输出:
1 6 13 14 15 16 17 19 20 22 23 25 27 28 29 30 31 32 35 36 38 39 41 42 45 46 47 49 55 57 58 67 68 69 70 73 75 76 78 84 85 87 88 89 91 94 99
2 7 18 26 48 50 56 74 79 90 92 95 100
3 8 21 33 59 77 80 96
4 9 24 34 60 97
5 10 61 98
11 62
12 63
37 64
40 65
43 66
44 71
51 72
52 81
53 82
54 83
86
93
我的输出:
1 6 13 14 15 16 17 19 20 22 23 25 27 28 29 30 31 32 35 36 38 39 41 42 45 46 47 49 55 57 58 67 68 69 70 73 75 76 78 84 85 87 88 89 91 94 99
2 7 18 26 48 50 56 74 79 90 92 95 100
3 8 21 33 59 77 80 96
4 9 24 34 60 97
5 10 61 98
11 62
12 63
37 64
40 65
43 66
44 71
51 72
52 81
53 82
54 83
86
93
肉眼fc和机器fc都表示这两个输出时一样的,而且同样的代码,我在其它oj上也测了,但我却过了:
难道是luogu的评测出问题了?想知道到底怎么个事,大家快帮我看一下