题解 P2695 【骑士的工作】

思路很简单，就是贪心~

神犇都用的排序

蒟蒻懒得手写了。

用的是最大值和最小值；

先检测头中的最大值；

再检测能杀这个头的最小值；

杀完之后勇士和头全部设成-1；这样就不会被选中了。

#include<stdio.h>
using namespace std;
int n;int m;int head[20001];int cost[20001];
int maxnum=20001;int minnum=20001;int res=0;//不存在的点，存放max和min的初始值
int main()
{   
    cost[20001]=999999;head[20001]=-1;//初始化。
    scanf("%d%d",&n,&m);
    if(n>m)//特判。
    {
        printf("you died!");
        return 0;
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&head[i]);
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d",&cost[i]);
    }
    while(1)//死循环，直到满足出来的条件用return结束整个程序
    {
        for(int i=0;i<n;i++)
        {
            if(head[maxnum]<head[i])
            {
              maxnum=i;
            }
        }    
        if(maxnum==20001)
        {
            printf("%d",res-999999);//头全部被砍光
            return 0;//拜拜程序~
        }
        for(int i=0;i<m;i++)
        {
            if(head[maxnum]<=cost[i])
            {   
                if(cost[minnum]>cost[i])minnum=i;
            }
        } 
        if(minnum==20001)
        {
                printf("you died!");//没有符合条件勇士。
                return 0;//拜拜程序~
        }
        else
        {
                res+=cost[minnum];
                cost[minnum]=-1;
                head[maxnum]=-1;
        }
        maxnum=20001;
        minnum=20001;
    }
    return 0;
}