今日头条笔试题--木棒拼图

Posted on

问题描述

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

示例 1

输入

1
2
3
4
5
6
5
1 1
1 1
1 1
2 1
1 2

输出

1
2
3
4
5
No
No
Yes
No
No

解题思路

  1. 边数大于等三
  2. 最长的边要大于其他边之和

首先很明显需要排序并且只关心最大的那条，所以一开始想到的是使用最大堆，但是这个最大堆又会被要求删除子节点。
因为最近在看AVL树，红黑树，B-tree等，知道C++的STL map底层实现是使用红黑树，那么就可以保证树的第一个是最小值，最后一个是最大值。

解题代码

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
#include <iostream>
#include <map>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    map<int, int> m;
    long long sum = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        int choice;
        int len;
        scanf("%d %d", &choice, &len);
        if (choice == 1) {
            m[len]++;
            count++;
            sum += len;
        } else {
            count--;
            if (--m[len] <= 0) {
                m.erase(len);
            }
            sum -= len;
        }
        if (count >= 3 && m.rbegin()->first < sum - m.rbegin()->first) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
}