题解 P2695 【骑士的工作】
shadowice1984
2017-09-15 17:19:41
思路很简单，就是贪心~
神犇都用的排序
蒟蒻懒得手写了。
用的是最大值和最小值；
先检测头中的最大值；
再检测能杀这个头的最小值；
杀完之后勇士和头全部设成-1；这样就不会被选中了。
```cpp
#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;
}
```