ZZULIOJ-2617: 体检

题目

2617: 体检时间限制: 1 Sec 内存限制: 128 MB 提交: 236 解决: 30

题目描述
VX玩了这么多游戏以后，感觉自己身体素质和智商都有所下降，所以决定去医院体检一下。
已知VX一共需要体检N项，并且每项体检需要时间一定的时间，并且每个项目体检时间还会随之增加。
请帮忙找出最优的体检顺序，并输出体检完所有项目的最短的总时长
输入
多实例
第一行读入T，表示共有T组数据（T=100)
接下来共有T行，每行一个整数N，表示体检的项目数（1<=N<=6)
接下里会有N行，每行两个数字（a,b)
a表示体检该项目共需a分钟
b表示当VX不在该项目时，该项目的体检时间每1分钟增加b分钟
输出
对于每组测试数据，输出一个整数，表示最短的总体检时间(保证最终答案在int范围内)
样例输入

样例输出 Copy

1
1419
66

提示
对于第二组测试数据，最优解法为：
1.先做第一项，该项耗时 1 分钟，总累计耗时1分钟
2.做第二项，该项耗时 2+31=5 分钟，总累计耗时6分钟
3.做第三项，该项耗时 3+46=27 分钟，总累计耗时33分钟
4.做第四项，该项耗时 4+533=169 分钟，总累计耗时202分钟
5.做第五项，该项耗时 5+6202=1217 分钟，总累计耗时1419分钟

解题思路

假设现在有两个项目需要检查分别是 A1 B1和 A2 B2,那么我们是如何选择呢，其实是用 A1+A1 * B2+A2 和 A2+A2*B1+A1 通过比较这两哪个的结果小先去看哪个，让后让我们拓展成 n 个，我们如何选择第一个呢？肯定也是这样比较的然后选择第二个，选择第二个的时候相当于每个之前的时间在这次比较的时候都加上了，对结果不影响。所以我们可以直接sort一波然后从前到后开始加就可以了

代码

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
	int x,y;
}a[10];
bool cmp(node a,node b)//进行排序 
{
	return (b.y +1)*a.x+b.x<(a.y+1)*b.x+a.x;
}
int main()
{
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&a[i].x,&a[i].y);
		}
		sort(a,a+n,cmp);
		int sum=0;
		for(int i=0;i<n;i++)
		sum+=a[i].x+sum*a[i].y;
		printf("%d\n",sum);
	}
	return 0;
 }