例1：排队接水

题目描述

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的等待时间 $T_i$。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

样例 #1

样例输入 #1

10 
56 12 1 99 1000 234 33 55 99 812

样例输出 #1

3 2 7 8 1 4 9 6 10 5
291.90

提示

$1\le n \leq 1000$，$1\le t_i \leq 10^6$，不保证 $t_i$ 不重复。

代码

#include<bits/stdc++.h>
using namespace std;

struct node{
	int time,id;
}a[1005];

int cmp(node x,node y){
	return x.time<y.time;
}
int main(void){
	int n;
	double k=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].time,a[i].id=i;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) cout<<a[i].id<<" ";
	for(int i=1;i<=n;i++){
		k+=i*a[n-i].time;
	}
	printf("\n%.2f",k/n);
	return 0;
}

例2：两人过河

题目描述

有 $n$ 个人希望在晚上通过一座桥。在任何时刻，最多只能有两个人在桥上，并且必须要带着手电简才能通过桥。现在的麻烦是只有一个手电筒，所以必须安排某种顺序，使得手电筒可以被带回去让更多的人过桥（手电筒必须由人带回，不可以从对岸扔过去）。

每个人都有不同的过桥时间，两个人一起过桥所用的时间等于其中较慢的一个。本题的任务是找出能在最短时间内使所有人都过桥的方案。

输入格式

第一行为一个整数 $n$。

接下来的 $n$ 行，每行给出一个人的过桥时间（整数，单位：秒）。

每个人的过桥时间不超过 $100$ 秒。

输出格式

输出一行一个数，表示所有人过桥的最短时间。

样例 #1

样例输入

4
1
2
5
10

样例输出

17

提示

样例说明

可以先让 $1$ 和 $2$ 过桥，然后 $1$ 回来，让 $5$ 和 $10$ 过桥，然后 $2$ 再回来带 $1$ 一起过桥，时间为$2+1+10+2+2=17$。

数据规模

对于 $40$% 的数据满足：$n≤100$。

对于 $100$% 的数据满足：$n≤1000$。

代码

#include<bits/stdc++.h>
using namespace std;

int a[1005],dp[1005];
int main(void){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	dp[1]=a[1];
	dp[2]=a[2];
	for(int i=3;i<=n;i++)
		dp[i]=min(dp[i-1]+a[1]+a[i],dp[i-2]+a[1]+a[2]*2+a[i]);
	cout<<dp[n]<<endl;
	return 0;
}

例3：大神排队

题目描述

现在共有 $n$ 个同学要排成一列，每个同学有两个属性：影响力和承受能力。给一个同学造成的心理创伤指数等于所有在他前面同学的影响力之和减去他的承受力。

请安排一下排队顺序，尽量使受到心理创伤最大的同学少受创伤。

输入格式

第一行是整数 $n$ ，表示同学人数。

第 $2$~$n+1$行，每行两个自然数，分别是该同学的影响力和承受能力。

输出格式

输出一行一个整数，为你安排的顺序中受到心理创伤最大的同学受到的创伤。

样例 #1

样例输入

3
10 3
2 5
3 3

样例输出

2

提示

对于 $100$% 的数据满足：$1≤n≤50000$，$1≤$ 影响力 $≤10000$，$1≤$ 承受能力 $≤10^9$。