Note: This article is available in Chinese only. 本文暂无英文版本。
View original
有一个由很多木棒构成的集合，每个木棒有对应的长度，请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上，简单多边形即不会自交的多边形。
初始集合是空的，有两种操作，要么给集合添加一个长度为 L 的木棒，要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。
输入描述：#
每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n 表示操作的数量(1 ≤ n ≤ 50000) ， 接下来有n行，每行第一个整数为操作类型 i (i ∈ {1,2})，第二个整数为一个长度 L(1 ≤ L ≤ 1,000,000,000)。如果 i=1 代表在集合内插入一个长度为 L 的木棒，如果 i=2 代表删去在集合内的一根长度为 L 的木棒。输入数据保证删除时集合中必定存在长度为 L 的木棒，且任意操作后集合都是非空的。
输出描述：#
对于每一次操作结束有一次输出，如果集合内的木棒可以构成简单多边形，输出 “Yes” ，否则输出 “No”。
输入例子：#
5
1 1
1 1
1 1
2 1
1 2
输出例子：#
No
No
Yes
No
No
能组成n边形的条件可以由三角形推广而来..(虽然只是猜想… 也就是n-1条较小边的和大于最大边…事实证明这结论是对的orz.. 然后就是multiset就好…
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年03月29日 星期三 21时17分02秒
4File Name :code/toutiao2.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n;
34multiset<long long>se;
35int main()
36{
37 #ifndef ONLINE_JUDGE
38 freopen("code/in.txt","r",stdin);
39 #endif
40 cin>>n;
41 while (n--)
42 {
43 LL x,y;
44 scanf("%lld%lld",&x,&y);
45 if (x==1) se.insert(y);
46 else se.erase(se.find(y));
47 if (se.size()<=2)
48 {
49 puts("No");
50 continue;
51 }
52 LL mx = -1;
53 LL sum = 0 ;
54 for ( auto it = se.begin() ; it!=se.end() ; it++)
55 {
56 sum = sum + *it;
57 if (*it>mx) mx = *it;
58 }
59 sum -=mx;
60 if (sum>mx)
61 {
62 puts("Yes");
63 }
64 else
65 {
66 puts("No");
67 }
68 }
69
70
71 #ifndef ONLINE_JUDGE
72 fclose(stdin);
73 #endif
74 return 0;
75}