我要招人

去企业版

首页 > 试题广场 >

木棒拼图

[编程题]木棒拼图

热度指数：3705 时间限制：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

输入

输出

No
No
Yes
No
No

算法知识视频讲解

查看答案及解析

推荐

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

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

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条回答 106收藏 16023浏览

通过挑战的用户

tsrj

2023-02-08 18:52:19
Elizabe...

2022-12-04 13:53:38
努力找工作的鼠鼠

2022-11-27 10:32:27
b0100_

2022-11-26 18:51:06
clwycash

2022-11-13 22:43:48

木棒拼图

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题