UVa 11729 Commando War

想法：B的總合是固定的，那麼要使得答案最小，就要盡量讓J的時間範圍重疊，因此將J由大排到小

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct soldier{
	int B;
	int J;
	}a[10001];
	bool cmp(soldier a,soldier b){
	return a.J > b.J;
	}
	int main()
	{
	int N,Case=1;
	while (scanf("%d",&N)){
	if (N == 0) break;
	for(int i=0;i<N;i++) scanf("%d%d",&a[i].B,&a[i].J);
	sort (a,a+N,cmp);
	int time=0;
	int ans=0;
	for (int i=0;i<N;i++) {
	time += a[i].B;
	ans = max(ans,time+a[i].J);
	}
	printf("Case %d: ",Case++);
	printf("%d\n",ans);
	}
	return 0;
	}

view raw [Uva] 11729 Commando War.cpp hosted with ❤ by GitHub