5 1 2 2 3 3 4 4 5 5 6 0
1419HintIn the Sample Input, WANGPENG just follow the given order. He spends 1 second in the first queue, 5 seconds in the 2th queue, 27 seconds in the 3th queue, 169 seconds in the 4th queue, and 1217 seconds in the 5th queue. So the total time is 1419s. WANGPENG has computed all possible orders in his 120-core-parallel head, and decided that this is the optimal choice.
题意：对于每个bi,除了第一个选择的，都是每秒加一个bi的，求最小的和。
我们考虑两个相邻的项目i,j:
(ai,bi),(aj,bj),在进行这两项检查时，这两个项目的先后顺序不会影响其它项目的消耗时间。
因此，我们只需要得出这两项先后关系就好了。若i<j，则ai+ai*bj+aj<aj+aj*bi+ai;即是(ai/bi)<(aj/bj);
按这个关系排序就OK了。
</pre><pre name="code" class="cpp">#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define N 100005
#define LL __int64
const LL mod=365*24*60*60;
struct node
{
int a,b;
double c;
}g[N];
bool cmp(node a,node b)
{
return a.c<b.c;
}
int main()
{
int i,n;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
{
scanf("%d%d",&g[i].a,&g[i].b);
g[i].c=1.0*g[i].a/g[i].b;
}
sort(g,g+n,cmp);
LL sum=0;
for(i=0;i<n;i++)
{
sum=(sum+sum*g[i].b+g[i].a)%mod;
}
printf("%I64d\n",sum);
}
return 0;
}
hdu 4442 Physical Examination (排序)
原文：http://blog.csdn.net/u011721440/article/details/40302639