题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6557
解题心得：
做法就是将输入的值按照升序排序，然后从小到大依次合并，例如
3
3
3和
3
3
3合并成
2
2
2，
4
4
4和
4
4
4合并成
3
3
3，用一个栈来模拟一下。如果能合并出两个
1
1
1那么输出
Y
E
S
YES
YES否则输出
N
O
NO
NO，如果只有一个
1
1
1那么无论栈中还剩下什么求和之后都一定小于二分之一，这里可以等比数列求和再求个极限就可以证明出来。在记录的时候合并起来变成
1
1
1的肯定是排序后连续的一段区间，只需要记录一下这个段区间就好。有一个小细节，只能从小到大合并，如果从大到小可能会漏掉这也很容易想到。在比赛的时候明明都有思路了开始敲了，队友一直和我说着说那，然后又怀疑我的思路，最后给我提供了个超级复杂的路径记录的方法，然后就写炸了。最后没办法写不下去了，删了代码，不理他BB，十多分钟就敲出来了，难受。
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int maxn
= 1e6+100;
struct Node
{
int va
, pos
;
bool operator
< (const Node
&x
) const {
if(va
!= x
.va
) return va
> x
.va
;
return pos
< x
.pos
;
}
}node
[maxn
];
int n
;
bool vis
[maxn
];
void init() {
scanf("%d", &n
);
for(int i
=1;i
<=n
;i
++) {
scanf("%d", &node
[i
].va
);
node
[i
].pos
= i
;
}
sort(node
+1, node
+1+n
);
}
stack
<pair
<int,int> > st
;
vector
<pair
<int,int> > ans
;
void solve() {
ans
.clear();
while(!st
.empty()) st
.pop();
for(int i
=1;i
<=n
;i
++) {
if(node
[i
].va
== 1) {
ans
.push_back(make_pair(i
, i
));
continue;
}
if(ans
.size() >= 2) break;
if(st
.empty()) {
st
.push(make_pair(node
[i
].va
, i
));
} else {
int va
= node
[i
].va
, pos
= i
;
while(!st
.empty() && va
== st
.top().first
&& va
!= 1) {
va
--;
pos
= st
.top().second
;
st
.pop();
}
if(va
== 1) {
ans
.push_back(make_pair(pos
, i
));
} else {
st
.push(make_pair(va
, pos
));
}
if(ans
.size() == 2) break;
}
}
if(ans
.size() < 2) {
printf("NO\n");
return ;
}
printf("YES\n");
for(int i
=ans
[0].first
;i
<=ans
[0].second
;i
++) {
vis
[node
[i
].pos
] = true
;
}
for(int i
=1;i
<=n
;i
++) {
if(vis
[i
]) {
printf("1");
vis
[i
] = false
;
} else {
printf("0");
}
}
printf("\n");
}
int main() {
int t
; scanf("%d", &t
);
int T
= t
;
while(t
--) {
init();
printf("Case %d: ", T
-t
);
solve();
}
return 0;
}
