木棒拼图

[编程题]木棒拼图

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

Java

只求一个offer！！！！

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Comparator<Integer> cmp = new Comparator<Integer>() {
            public int compare(Integer e1, Integer e2) {
                return e2 - e1;
            }
        };
        PriorityQueue<Integer> queue = new PriorityQueue<>(cmp);

        while (in.hasNext()){
            int n = in.nextInt();
            int shape =0;

            for (int i = 0; i < n ; i++) {
               int just = in.nextInt();
                int l = in.nextInt();
                if(just == 1){
                    queue.add(l);
                }else {
                    queue.remove(l);
                }
                shape = queue.peek();
                List<Integer> list = new ArrayList<>(queue);
                if(list.size()>=3){
                    int len = 0;
                    for (int j = 0; j < list.size() ; j++) {
                        len+= list.get(j);
                    }
                    if((len-shape)>shape){
                        System.out.println("Yes");
                    }else {
                        System.out.println("No");
                    }
                }else {
                    System.out.println("No");
                }
            }
        }
    }
}

发表于 2020-07-12 21:43:19 回复(0)

Java

是王博

import java.security.PublicKey;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int num = 0;
        int j = 0;
        int max = 0;

        List<Integer> list = new ArrayList<>();
        while (j++ < n) {
            int i = sc.nextInt();
            int l = sc.nextInt();
            sc.nextLine();
            if (i == 1) {
                list.add(l);
                num += l;
            } else {
                list.remove(list.indexOf(l));
                num -= l;
            }
            Collections.sort(list);
            
            if(list.size() > 0){
                max = list.get(list.size()-1);
            }
            if (num - max <= max) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }
        }
    }
}

发表于 2020-05-19 17:38:42 回复(0)

Java

牛客199131294号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> ls= new ArrayList<>();
        for (int i=0;i<n;i++){
            int op = sc.nextInt();
            int length = sc.nextInt();
            if (op==1){
                ls.add(length);
            }else{
                int idx = ls.indexOf(length);
                ls.remove(idx);
            }
            if (ls.size() < 3){
                System.out.println("No");
            }else{
                Collections.sort(ls,Collections.reverseOrder());
                int max = ls.get(0);
                int sum = 0;
                for (int j=1;j<ls.size();j++){
                    sum += ls.get(j);
                }
                if(sum>max){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
    }
}

平民算法。。。

编辑于 2020-01-07 15:19:19 回复(1)