今日头条笔试题-木棒拼图(数学)

2017-03-29 · 2 min read · math

有一个由很多木棒构成的集合，每个木棒有对应的长度，请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 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"。

输入例子:

输出例子:

No
No
Yes
No
No

能组成n边形的条件可以由三角形推广而来..(虽然只是猜想... 也就是n-1条较小边的和大于最大边...事实证明这结论是对的orz.. 然后就是multiset就好...

/* ***********************************************
Author :111qqz
Created Time :2017年03月29日 星期三 21时17分02秒
File Name :code/toutiao2.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6int n;
 7multiset<long long>se;
 8int main()
 9{
10	#ifndef  ONLINE_JUDGE 
11	freopen("code/in.txt","r",stdin);
12  #endif
13	cin>>n;
14	while (n--)
15	{
16	    LL x,y;
17	    scanf("%lld%lld",&x,&y);
18	    if (x==1) se.insert(y);
19	    else se.erase(se.find(y));
20	    if (se.size()<=2)
21	    {
22		puts("No");
23		continue;
24	    }
25	    LL mx = -1;
26	    LL sum = 0 ;
27	    for ( auto it = se.begin() ; it!=se.end() ; it++)
28	    {
29		sum = sum + *it;
30		if (*it>mx) mx = *it;
31	    }
32	    sum -=mx;
33	    if (sum>mx)
34	    {
35		puts("Yes");
36	    }
37	    else
38	    {
39		puts("No");
40	    }
41	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}