抽屉问题吃糖果

以你之姓@ 2021-11-01 14:40 328阅读 0赞

Problem Description

HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种，这样；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下。

Input

第一行有一个整数T，接下来T组数据，每组数据占2行，第一行是一个整数N（0<N<=1000000)，第二行是N个数，表示N种糖果的数目Mi(0<Mi<=1000000)。

Output

对于每组数据，输出一行，包含一个"Yes"或者"No"。

Sample Input

2 3 4 1 1 5 5 4 3 2 1

Sample Output

No Yes

1.贪心+ 堆

2.插板法 当maxx-1<=sum 时 一定行 否则不行

//
    #include<bits/stdc++.h>
    using namespace std;
    priority_queue <int > Q;
    int T,m,n;
    
    int main()
    {
        cin>>T;
        int x;
        while(T--)
        {
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                cin>>x;
                Q.push(x);
            }
            int fla=0;
            while(Q.size())
            {
                int s=Q.top();
                Q.pop();
                s--;
                while(Q.size()&&s)
                {
                    int k=Q.top();
                    Q.pop();
                    if(s<k)
                    {
                        Q.push(k-s);
                        s=0; 
                    } 
                    else
                    {
                        s-=k;
                    }
                }
            if(s!=0)
            {
                cout<<"No"<<endl;
                fla=1;
            }
        }
            if(fla==0) cout<<"Yes"<<endl;
        }
        
        
    }

转载于:https://www.cnblogs.com/OIEREDSION/p/11308441.html

发表评论取消回复

表情：

评论列表（有 0 条评论，328人围观）

还没有评论，来说两句吧...

相关阅读

相关 android 抽屉_Android导航抽屉教程

![c0ebdc8967049202797d383f886bf329.png][] android 抽屉 In this tutorial you will learn a

r囧r小猫/ 2022年12月08日 04:46/ 0 赞/ 276 阅读

相关 HDOJ 1205-吃糖果【思维】

吃糖果 Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

客官°小女子只卖身不卖艺/ 2022年08月21日 03:20/ 0 赞/ 165 阅读

相关我爱吃糖果

我爱吃糖果 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述圣诞节快到了，金菊巨意外

男娘i/ 2022年08月19日 02:21/ 0 赞/ 185 阅读

相关小鑫吃糖果

小鑫吃糖果 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述小鑫是个吃货，妈妈给他买了好多的

左手的ㄟ右手/ 2022年08月14日 05:38/ 0 赞/ 170 阅读

相关 1146: 吃糖果

Description HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖果时有个特殊的癖好，就是不喜欢连续两次吃一样的糖果，喜欢先吃一颗A种类的

╰+攻爆jí腚メ/ 2022年06月11日 02:06/ 0 赞/ 237 阅读

相关站队问题、分糖果问题

站队问题分糖果 -------------------- 站队问题 n个人站队，他们的编号依次从1到n，要求编号为a的人必须

╰半橙微兮°/ 2022年06月09日 10:00/ 0 赞/ 238 阅读

相关 hdu-1205 吃糖果

吃糖果 Problem Description HOHO，终于从

本是古典何须时尚/ 2022年03月19日 09:38/ 0 赞/ 206 阅读

相关 1193：吃糖果

1193：吃糖果时间限制: 1000 ms 内存限制: 65536 KB 提交数: 3415 通过数: 2719 【题目描述】名名的妈妈从外地出差回

梦里梦外;/ 2022年01月12日 07:59/ 0 赞/ 372 阅读

相关抽屉问题吃糖果

Problem Description HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先

以你之姓@/ 2021年11月01日 14:40/ 0 赞/ 329 阅读

相关重构-抽屉(左右抽屉)

动画: 抽屉出现背景渐变抽屉出现消失移动动画实现: display从none到block产生过渡动画:使用anim

妖狐艹你老母/ 2021年07月24日 16:52/ 0 赞/ 443 阅读