“Waiting for orders we held in the wood, word from the front never came

By evening the sound of the gunfire was miles away

Ah softly we moved through the shadows, slip away through the trees

Crossing their lines in the mists in the fields on our hands and our knees

And all that I ever, was able to see

The fire in the air, glowing red, silhouetting the smoke on the breeze”

There is a war and it doesn't look very promising for your country. Now it's time to act. You have a commando squad at your disposal and planning an ambush on an important enemy camp located nearby. You have N soldiers in your squad. In
your master-plan, every single soldier has a unique responsibility and you don't want any of your soldier to know the plan for other soldiers so that everyone can focus on his task only. In order to enforce this, you brief every individual soldier about his
tasks separately and just before sending him to the battlefield. You know that every single soldier needs a certain amount of time to execute his job. You also know very clearly how much time you need to brief every single soldier. Being anxious to finish
the total operation as soon as possible, you need to find an order of briefing your soldiers that will minimize the time necessary for all the soldiers to complete their tasks. You may assume that, no soldier has a plan that depends on the tasks of his fellows.
In other words, once a soldier  begins a task, he can finish it without the necessity of pausing in between.

Input

There will be multiple test cases in the input file. Every test case starts with an integer N (1<=N<=1000), denoting the number of soldiers. Each of the following N lines describe a soldier with two integers B (1<=B<=10000) & J
(1<=J<=10000). B seconds are needed to brief the soldier while completing his job needs J seconds. The end of input will be denoted by a case with N =0 . This case should not be processed.

Output

For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the total number of seconds counted from the start of your first briefing till the completion of all jobs.

Sample Input                                               Output for Sample Input

Problem Setter: Mohammad Mahmudur Rahman, Special Thanks: Manzurur Rahman Khan

按照执行时间排序，贪心

可以画图验证。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (1000+10)
#define MAXBi (10000+10)
#define MAXJi (10000+10)
struct arr
{
	int a,b;
	friend bool operator<(arr a,arr b){return a.b>b.b;	}
}a[MAXN];
int n;
int main()
{
	int t=1;
	while (scanf("%d",&n)!=EOF&&n)
	{
		for (int i=1;i<=n;i++) scanf("%d%d",&a[i].a,&a[i].b);
		sort(a+1,a+n+1);
		int p=0,ans=0;
		for (int i=1;i<=n;i++)
		{
			p+=a[i].a;
			ans=max(ans,p+a[i].b);
		}
		printf("Case %d: %dn",t++,ans);
	}
	return 0;
}

Problem C: The Dragon of Loowater

Once upon a time, in the Kingdom of Loowater, a minor nuisance turned into a major problem.

The shores of Rellau Creek in central Loowater had always been a prime breeding ground for geese. Due to the lack of predators, the geese population was out of control. The people of Loowater mostly kept clear of
the geese. Occasionally, a goose would attack one of the people, and perhaps bite off a finger or two, but in general, the people tolerated the geese as a minor nuisance.

One day, a freak mutation occurred, and one of the geese spawned a multi-headed fire-breathing dragon. When the dragon grew up, he threatened to burn the Kingdom of Loowater to a crisp. Loowater had a major problem.
The king was alarmed, and called on his knights to slay the dragon and save the kingdom.

The knights explained: "To slay the dragon, we must chop off all its heads. Each knight can chop off one of the dragon's heads. The heads of the dragon are of different sizes. In order to chop off a head, a knight
must be at least as tall as the diameter of the head. The knights' union demands that for chopping off a head, a knight must be paid a wage equal to one gold coin for each centimetre of the knight's height."

Would there be enough knights to defeat the dragon? The king called on his advisors to help him decide how many and which knights to hire. After having lost a lot of money building Mir Park, the king wanted to minimize
the expense of slaying the dragon. As one of the advisors, your job was to help the king. You took it very seriously: if you failed, you and the whole kingdom would be burnt to a crisp!

Input Specification:

The input contains several test cases. The first line of each test case contains two integers between 1 and 20000 inclusive, indicating the number n of heads that the dragon has, and the number m of
knights in the kingdom. The next n lines each contain an integer, and give the diameters of the dragon's heads, in centimetres. The following m lines each contain an integer, and specify the heights of the knights of Loowater, also in centimetres.

The last test case is followed by a line containing:

0 0

Output Specification:

For each test case, output a line containing the minimum number of gold coins that the king needs to pay to slay the dragon. If it is not possible for the knights of Loowater to slay the dragon, output the line:

Loowater is doomed!

Sample Input:

2 3
5
4
7
8
4
2 1
5
5
10
0 0

Output for Sample Input:

11
Loowater is doomed!

让最差的骑士优先杀最差的，

否则这个骑士不取。

可以证明这样取最优。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20000+10)
int n,m,a[MAXN],b[MAXN];
int main()
{
	while (scanf("%d%d",&n,&m)&&n&&m)
	{
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		for (int i=1;i<=m;i++) scanf("%d",&b[i]);
		sort(a+1,a+n+1);sort(b+1,b+m+1);
		int i=1,j=1,cost=0;
		for (;i<=n&&j<=m;i++,j++)
		{
			if (b[j]>=a[i]) cost+=b[j];
			else i--;
		}
		if (i>n) cout<<cost<<endl;
		else cout<<"Loowater is doomed!n";
	}
	return 0;
}

Description

 第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，n号选手捉对厮杀，共进行n场比赛。每胜一场比赛得2分，平一场得1分，输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。
作为浙江队的领队，你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚，并将其用一个实力值来衡量。为简化问题，我们假定选手在游戏中完全不受任何外界因素干扰，即实力强的选手一定可以战胜实力弱的选手，而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序，所以所有的队伍都采取了这样一种策略，就是完全随机决定出场顺序。 当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下，浙江队最终分别能得到多少分。

Input

Output

Sample Input

Sample Output

田忌赛马加强版。

尽可能让最弱的赢，最强的赢，都不行则最弱打最强

错误的贪心：

让最弱的能赢/平则赢/平，否则让其与最强的打

反例：

2

1 2 6 7

1 2 4 7

 ans1=6

反例ans1=5

最差情况：

容易发现2个队伍的总分一定(2-0,1-1,0-2)

 所以ans2=2n-B队最高分

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN],b[MAXN];
int calc()
{
	int i=1,j=1,k=n,l=n,ans=0;
	while (i<=k)
	{
		if (a[i]>b[j]) ans+=2,i++,j++;
		else if(a[k]>b[l]) ans+=2,k--,l--;
		else ans+=(a[i]==b[l]),i++,l--;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	sort(a+1,a+1+n);sort(b+1,b+1+n);
	cout<<calc()<<' ';
	swap(a,b);
	cout<<2*n-calc()<<endl;
	return 0;
}

4
2 1 6 4
3 4 4 2

3

4
10 5 6 4
1 11 4 2

6

3
10 1 10
1 10 1 1

3

显然除了直接移(先行后列）外，

唯一减少操作数的方法便是向中间以外的行数移，以求降低列的移动数。

一定要注意不是挪到每行直接取abs(行尾-c2)的，因为可能会有往返行尾的路上有更小的，直接取行尾可能拉近它和c2的距离，但是这种操作是不可行的。

#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (10000+100)
int a[MAXN],n;
int abs2(int a,int b)
{
	if (a<b) return b-a;
	else return a-b;
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int r1,c1,r2,c2;
	scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
	int mi=c1,ans=0,tans=1000000000;
	if (r1<r2)
	{
		ans=r2-r1;
		for (int i=r1+1;i<=r2;i++) mi=min(mi,a[i]+1);
		tans=min(tans,ans+abs(mi-c2));
		for (int i=r1-1,cost=2,mii=mi;i>=1;i--,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
		for (int i=r2+1,cost=2,mii=mi;i<=n;i++,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
	}
	else
	{
		ans=r1-r2;
		for (int i=r1-1;i>=r2;i--) mi=min(mi,a[i]+1);
		tans=min(tans,ans+abs(mi-c2));
		for (int i=r2-1,cost=2,mii=mi;i>=1;i--,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
		for (int i=r1+1,cost=2,mii=mi;i<=n;i++,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
	}
	cout<<tans<<endl;
	return 0;
}