hdoj 1800 Flying to the Mars【贪心】

末蓝、 2022-08-04 13:41 8阅读 0赞

# Flying to the Mars #

**Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 14726    Accepted Submission(s): 4747**

【本文写的是贪心解法，还有其他解法下次补进】

Sample Input

4
    10
    20
    30
    04
    5
    2
    3
    4
    3
    4

Sample Output

1
    2

题目大意：有n个人，每个人都有自己的等级，他们想学哈利波特骑扫帚的技术，等级高的可以教等级低的，且等级相同的不能用同一个扫帚，问最少需要多少扫帚？

例如 ：  
有5个兵（ABCDE） 等级分别是：2 4 5 6 4;  
一种方法：  
让C教B：B可以教A;因此，C、B、A可以在同一个扫帚训练。  
D教E;因此DE可以在同一个扫帚训练;  
使用这种方法，我们需要2扫帚。  
另一种方法：  
D教A;因此，AD可以在同一个扫帚训练。  
让C教B：所以BC可以在同一个扫帚训练。  
E没有老师或学生，固E需要另外在拿一个扫帚训练。  
使用该方法，我们需要3扫帚。

思路：求出拥有同等级最多的人数

首先进行排序（笔者按从小到大排），然后记录每个等级都有几多人，取最多人的那一组，这组的人数就是扫帚最小需求量：

【注意：本题和最少拦截系统有点像相似，但又有不同，最大的不同是，导弹那一题，导弹飞来的顺序是固定的，不可以改变其顺序，而本题可以改变顺序】；

已Accept代码（c++提交）

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int k[3005];
    int main(){
        int n,i;
        while(scanf("%d",&n)!=EOF){
            memset(k,0,sizeof(k));
            for(i=0;i<n;i++)
                scanf("%d",&k[i]);
            sort(k,k+n);		//排序，sort默认的从小到大排序 
            int maxn=1,t=1;
            for(i=1;i<n;i++){
                if(k[i-1]==k[i])//判断第i-1个人是否与第i个人是同级的，若是，记录加一； 
                    t++;
                else
                    t=1;
                if(maxn<t)//记录  等级人数  最多的  那一组的  人数 
                    maxn=t;
            }
            printf("%d\n",maxn);
        }
        return 0;
    }