Commando War(排序贪心)
Commando War
UVA - 11729 (题目链接)
题目描述:
解题思路:
该题利用贪心算法将任务时间由长到短贪心即可得到最短时间!
代码如下:
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#define inf 1e6+5
using namespace std;
typedef long long ll;
struct war
{
int a,b;
}arr[100000];
bool cmp(war A,war B)
{
return A.b>B.b;
}
int main()
{
int num=0,n;
while(~scanf("%d",&n))
{
if(n==0)
break;
int max1=0,ans=0;
for(int i=1;i<=n;i++)
scanf("%d%d",&arr[i].a,&arr[i].b);
sort(arr+1,arr+1+n,cmp);
for(int i=1;i<=n;i++)
ans+=arr[i].a,max1=max(ans+arr[i].b,max1);
printf("Case %d: %d\n",++num,max1);
}
return 0;
}
小试牛刀:
熟悉掌握贪心算法后,快去找一些贪心练习题加深自己的记忆吧!!!!