首页 > 试题广场 >

木棒拼图

[编程题]木棒拼图
  • 热度指数：3757 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

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

输入

5
1 1
1 1
1 1
2 1
1 2

输出

No
No
Yes
No
No
算法知识视频讲解
添加回答
推荐
D_L头像 D_L
判断几条棍子能否组成面积大于 0 的简单多边形只需满足一个条件：

木棍集合中找出一根最长的，记为 max_len
除了这一根外，剩下的长度之和，记为 Len

则必须满足 Len > max_len 。

换言之， 设总长度为 Tlen，
则仅当 Tlen - max_len > max_len 时，才能组成面积大于0 的简单多边形

那剩下的编程就简单多了 

#include <iostream>
#include <list>
using namespace std;

const char* is_ok(const list<size_t>& stick_set) {
    size_t sum = 0, max_len = 0;
    for (auto& v : stick_set) {
        if (v > max_len) {
            max_len = v;
        }
        sum += v;
    }
    if (sum - max_len <= max_len)
    	return "No";
    else
        return "Yes";
}

int main() {
    size_t n = 0;
    cin >> n;
    
    list<size_t> stick_set;
    while (n--) {
        int opt = 0;
        size_t len = 0;
        cin >> opt >> len;
        
        if (opt == 1) {
            // 增加一个 len
        	stick_set.push_back(len);
        }
        else if (opt == 2) {
            // 删除一个 len
            auto&& it = stick_set.begin();
            for (; it != stick_set.end(); ++it) {
                if (*it == len) {
                    stick_set.erase(it);
                    break;
                }
            }
            if (it == stick_set.end()) cout << "Error\n"; // not found
        }
        else {
            cout << "Error\n"; // Illegal value
        }
        
        cout << is_ok(stick_set) << endl;
        
    }
    return 0;
}


有些人可能会对简单多边形的数学概念有些模糊，举几个图例就明白了：

左边为简单多边形，右边为复杂多边形；
还有自相交多边形：


--------------------------------

代码可以继续优化，因为每插入或删除一个元素，都要调用 is_ok() 来遍历链表 求最大值 和 总长度，这是没有必要的；可以在元素插入时就形成一个 有序集合，同时记录 总长度，这样就不用 遍历的方式求最大值了。

优化后的代码： 

#include <iostream>
#include <set>
using namespace std;

int main() {
    size_t n = 0;
    cin >> n;

    // 木棍集合
    multiset<size_t> stick_set;

    size_t sum_len = 0; // 木棍集合中的总长度
    while (n--) {
        int opt = 0;
        size_t len = 0;
        cin >> opt >> len;

        if (opt == 1) { // 增加一个 len
            stick_set.insert(len);
            sum_len += len;
        }
        else if (opt == 2) { // 删除一个 len
            auto&& it = stick_set.find(len);
            if (it == stick_set.end()) {
                cout << "Error\n"; // not found
            }
            else {
                stick_set.erase(it);
                sum_len -= len;            
            }
        }
        else { // Illegal value
            cout << "Error\n";
        }

        const size_t max_len = *(stick_set.rbegin());
        cout << ((sum_len - max_len > max_len) ? "Yes" : "No") << endl;
    }
    return 0;
}

编辑于 2016-10-21 14:08:48 回复(3)
Python
LuckyBro头像 LuckyBro 
container = []
n = int(input())
while n > 0:
    i, L = list(map(int, input().split()))
    if i == 1:
        container.append(L)
        if len(container) <= 2:
            print("No")
        else:
            if max(container) < sum(container) - max(container):
                print("Yes")
            else:
                print("No")
    else:
        container.remove(L)
        if len(container) <= 2:
            print("No")
        else:
            if max(container) < sum(container) - max(container):
                print("Yes")
            else:
                print("No")
    n -= 1
编辑于 2020-09-21 22:32:22 回复(0)
Python
KMartinXu头像 KMartinXu 
ops=int(input())
sticks=[]
act=[]
maxlen=0
totallen=0
flag=True
for i in range(ops):
    Strinput =input()
    act =Strinput.split()
    #操作部分
    ifact[0]=='1':
        sticks.append(int(act[1]))
        totallen+=int(act[1])
    ifact[0]=='2':
        sticks.remove(int(act[1]))
        totallen-=int(act[1])
    maxlen=max(sticks)
    #判断部分
    ifmaxlen<totallen-maxlen:
        flag=True
    else:
        flag=False
    iflen(sticks)<3:
        flag=False
    ifflag==True:
        print('Yes')
    else:
        print('No')

用蟒蛇的时候偶尔偷偷懒用用自带函数也挺好的

发表于 2019-03-17 18:25:46 回复(0)
提交观点

问题信息

C++工程师 2017 运维工程师 前端工程师 算法工程师 PHP工程师 字节跳动 堆 排序 Java工程师
来自：字节跳动2017后端工...
难度：
2条回答 18947浏览

热门推荐

通过挑战的用户

相关试题

木棒拼图

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号