NOIP 2007 纪念品分组(贪心)

ゝ一世哀愁。 2022-05-16 02:13 229阅读 0赞

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。  
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入

每组输入数据包含n+2行：  
第1行包括一个整数w，为每组纪念品价格之和的上限。  
第2行为一个整数n，表示购来的纪念品的总件数。  
第3~n+2行每行包含一个正整数Pi（5<=Pi<=w），表示所对应纪念品的价格。  
  
  
数据规模：  
50%的数据满足：1<=n<=15；  
100%的数据满足：1<=n<=30000，80<=W<=200。

输出

每组输出仅一行，包含一个整数，即最少的分组数目。

分析：这题和 CodeForces158B Taxi很相似，有个不同的地方在于这题每组最多两个纪念品，所以加一个判断条件即可，

思路参考我[这篇博客][Link 1]。。。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    const int maxn=2e2+7;
    int vis[maxn],w,n;
    
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    void init()
    {
        Clear(vis);
    }
    
    void input()
    {
        int a;
        w=read(),n=read();
        fup(i,0,n)
        {
            a=read();
            vis[a]++;
        }
    }
    
    void slove()
    {
        int now,ans=0;
        while(n){
            now=w;
            ans++;
            int cnt=0;
            rfdn(i,w,5){
                while(vis[i]&&now>=i){
                    if(cnt>=2) break;//每组最多两个纪念品
                    now-=i;
                    vis[i]--;
                    n--;
                    cnt++;
                }
            }
        }
        printf("%d\n",ans);
    }
    
    int main()
    {
        int cas=1;
        while(cas--){
            init();
            input();
            slove();
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_41311604/article/details/81667557