首页 > 试题广场 >

木棒拼图

[编程题]木棒拼图

热度指数：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

算法知识视频讲解

牛客66666666号

#include <iostream>

using namespace std;

class Node
{
public:
	Node(int value)
	{
		val = value;
		next = NULL;
	}
	int val;
	Node* next;
};

long long int sum = 0;

void insert(int val, Node* root)
{
	Node* pre = root;
	Node* head = root->next;
	while(head)
	{
		if(head->val > val)
		{
			pre = pre->next;
			head = head->next;
		}
		else
			break;
	}
	Node* tmp = new Node(val);
	pre->next = tmp;
	tmp->next = head;
	sum += val;
}

void remove(int val, Node* root)
{
	Node* pre = root;
	Node* head = root->next;
	while(head)
	{
		if(head->val != val)
		{
			pre = pre->next;
			head = head->next;
		}
		else
			break;
	}
	pre->next = head->next;
	delete head;
	sum -= val;
}

int main()
{
	int n;
	cin>>n;
	Node* vir = new Node(0);  // 虚拟的头
	for(int i = 0; i < n; i++)
	{
		int val, cmd;
		cin>>cmd>>val;
		if(cmd == 1)
			insert(val, vir);
		else
			remove(val, vir);
		if(vir->next->val < sum - vir->next->val)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	//system("pause");
	return 0;
}

编辑于 2016-04-29 17:34:23 回复(0)

更多回答

推荐

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)

Alex-大伟

import java.util.ArrayList;
import java.util.Scanner;

public class DailyNews2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int[][] op = new int[n][2];
			for (int i = 0; i < n; i++) {
				op[i][0] = scanner.nextInt();
				op[i][1] = scanner.nextInt();
			}
			stickPuzzle(n, op);
		}
	}

	public static void stickPuzzle(int n, int[][] op) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			if (op[i][0] == 1) {
				list.add(op[i][1]);
			} else {
				list.remove(new Integer(op[i][1]));
			}
			if (canFormPoly(list)) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
	}
	//判断能否构成多边形  
	//list：各边长
	public static boolean canFormPoly(ArrayList<Integer> list) {
		int len = list.size();
		for (int i = 0; i < len; i++) {
			int temp = list.remove(i);
			int sum = 0;
			for (int j = 0; j < len - 1; j++) {
				sum += list.get(j);
			}
			if (sum <= temp) { //判断是否任意len-1条边之和大于剩余一条边
				list.add(i, temp);
				return false;
			}
			list.add(i, temp);
		}
		return true;
	}
}

编辑于 2016-10-01 23:05:21 回复(1)

最爱吃土豆hh

#include <iostream>
#include <string>
#include <map>
using namespace std;
map<int, int, greater<int>> mp;
int num = 0;
long long sum = 0;
 
string solution(int a, int b) {
    if (a == 1) {
        mp[b] ++;
        num++;
        sum += b;
    }
    else {
        if (mp[b] == 1)
            mp.erase(b);
        else {
            mp[b] --;
        }
        num--;
        sum -= b;
    }
    if (num <= 2) return "No";
    map<int, int>::iterator it = mp.begin();
    int maxa = it->first;
    if (maxa < sum - maxa) return "Yes";
    else return "No";
}
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        cout << solution(a, b) << endl;
    }
}

发表于 2022-04-09 16:09:47 回复(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)

etinnebezout

n = int(input())
r = []
while n>0:
    op, l = [int(ele) for ele in input().split(' ')]
    if op==1:
        r.append(l)
    else:
        r.remove(l)
    if len(r)<=2:
        print('No')
    else:
        if sum(r)>2*max(r):
            print('Yes')
        else:
            print('No')

    n-=1

发表于 2019-09-12 15:19:10 回复(0)

yunhe

木棍长度用long存储，否则会报数组越界
package leetcode.exams.toutiao;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/*
 * mind long is very important
 */
public class StickPuzzle {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			long[][] data=new long[n][2];
			for(int i=0;i<n;i++){
				data[i][0]=sc.nextLong();
				data[i][1]=sc.nextLong();
			}
			dealWith(data);
		}
	}
	
	public static void dealWith(long[][] data){
		List<Long> sticks=new ArrayList<Long>();
		for(int i=0;i<data.length;i++){
			if(data[i][0]==1)
				sticks.add(data[i][1]);
			else
				sticks.remove(data[i][1]);
			judge(sticks);
		}
	}
	
	public static void judge(List<Long> sticks){
		if(sticks.size()<3)
			System.out.println("No");
		else{
			Collections.sort(sticks);
			long sum=0;
			int i=0;
			for(i=0;i<sticks.size()-1;i++){
				sum+=sticks.get(i);
			}
			if(sum>sticks.get(i))
				System.out.println("Yes");
			else
				System.out.println("No");
		}
	}
}

发表于 2016-08-05 23:53:49 回复(10)

fcq1129

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

int main(){
	int n, sumLength; list<int> ls; 
	cin >> n;
	while(n--){
		int i, L;
		cin >> i >> L;
		
		if(i == 1) {
			sumLength += L;
			ls.push_back(L);
		}
		if(i == 2) {
			sumLength -= L;
			list<int>::iterator it = find(ls.begin(), ls.end(), L);
//			list<int>::iterator it = ls.find(L);
			ls.erase(it);
		}
//		
//		if(ls.size() < 3) {
//			cout << "NO" << endl;
//			continue;
//		}
		int maxLength = 0;
		for(list<int>::iterator it = ls.begin(); it !=ls.end(); it++) {
			if(maxLength < *it) maxLength = *it;
		} 
		if(sumLength-maxLength > maxLength) cout << "YES" << endl;
		else cout << "NO" << endl;
		
//		n--;		
	} 
	return 0;
}
求教：为什么我的输出只有一行？？

发表于 2016-06-05 10:37:20 回复(5)

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)

牛客710093887号

排序并且记录sum，出入排序，并且重新计算sum,以及最后一个值，即最大值，最大值大于等于sum二分之一，不能组成多边形

发表于 2022-11-22 17:35:22 回复(0)

#include#incl#i

啦。。

发表于 2022-10-14 21:45:26 回复(0)

牛客0X0001号

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, op, len;
    long long sum = 0;
	cin >> n;
    multiset<int> st;
	while (n--) {
        scanf("%d%d", &op, &len);
        if (op == 2) {
            st.erase(st.find(len));
            sum -= len;
        }
        else {
            st.insert(len);
            sum += len;
        }
        if (st.empty()) cout << "No\n";
        else {
            int t = *st.rbegin();
            if (sum-t > t && st.size() > 2) cout << "Yes\n";
            else cout << "No\n";
        }
    }
}

发表于 2020-12-06 16:29:35 回复(0)

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)

牛客181464990号

插入元素，然后对元素进行排序，将最大的元素拧出来，比较最大元素maxl和除去最大元素剩余元素之和suml，如果maxl<suml则输出Yes，否则输出No

发表于 2020-09-02 08:34:12 回复(0)

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)

行者201904091856381

把这个多边形看成一个三角形；把集合里长度最大的拿出来，再把剩下的所有边相加，只要这些边的长度之和大于最长的那边，就可以组成一个三角形；多边形是由三边或三边以上的边构成的。

发表于 2019-04-25 12:29:40 回复(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)

菜包子的噪声

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int n = scan.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i=0; i<n; i++){
if(scan.nextInt() == 1){
list.add(scan.nextInt());
}else{
list.remove((Object)scan.nextInt());
}
canConstruct(list);
scan.nextLine();
}
}
}

public static void canConstruct(ArrayList<Integer> list){
if(list.size()<3){
System.out.println("No");
return;
}
Collections.sort(list);
int len=list.size(), sum=0;
for(int i=0; i<len-1; i++){
sum+=list.get(i);
}
if(sum<=list.get(len-1)){
System.out.println("No");
}else{
System.out.println("Yes");
}
}
}

发表于 2019-01-10 15:21:40 回复(0)

sxy98

能够构成简单多边形要满足的条件：

①木棍要多于两根

②木棍中最长的一根要小于其他所有木棍长度之和（其实可以看做三角形）

所以，我们需要的数据是：

①剩余木棍根数

②剩余最长木棍长度max

③所有木棍长度之和sum

①和③是容易得到的，看②如何得到：

定义两个优先队列insert和del：

操作为1的时候向insert里插入木棍长度

操作为2的时候向del里插入木棍长度

要知道剩余最长木棍的长度，只需要判断insert.top和del.top是否相等，相等则都pop；不等，max=insert.top

每次操作完成后进行判断：

①insert队列长度是否比del队列长3及以上

②max是否大于sum-max

都满足输出yes，否则输出no

发表于 2018-12-17 10:53:21 回复(0)

社会王不爱编程

package com.itshw;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class test02 {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> list=new ArrayList<>();
        int i=0;
        while (n>0){
            int op=sc.nextInt();
            int l=sc.nextInt();
            if(op==1){
                list.add(l);
                canForm(list);
            }
            if(!list.isEmpty()&&op==2&&list.contains(l)){
                int index=list.indexOf(l);
                list.remove(index);
                canForm(list);
            }
            n--;
        }
    }

    private static void canForm(List<Integer> list) {
        if(list.isEmpty()||list.size()<3){
            System.out.println("No");
            return;
        }
        int sum=0;
        int max=list.get(0);
        for(int i=0;i<list.size();i++){
            int temp=list.get(i);
            sum+=temp;
            if(temp>max){
                max=temp;
            }
        }
        if(max<sum-max){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}

发表于 2018-09-21 20:35:14 回复(0)

shal

利用c++的红黑树map

#include <iostream>
#include <map>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    map<long long, long long> 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");
        }
    }
}

发表于 2018-04-24 15:00:46 回复(0)

冋宇同桌

堆优化

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

priority_queue<long long int> pq;
long long int sum, l;
int a;
long long int b;
map<long long int, int> countt;
int nowcount;
int main() {
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    sum = 0;
    nowcount = 0;
    while(n -- ) {
        cin >> a >> b;
        if (a == 1) {
            pq.push(b);
            sum += b;
            countt[b] ++;
            nowcount ++;
        } else {
            nowcount --;
            countt[b] --;
            sum -= b;
        }
        if (nowcount < 3) {
            puts("No");
            continue;
        }
        long long int temp = pq.top();
        while(countt[temp] == 0) {
            pq.pop();
            temp = pq.top();
        }
        if (sum - temp > temp) {
            puts("Yes");
        } else {
            puts("No");
        }

    }
    return 0;
}

发表于 2018-03-24 15:37:22 回复(0)