hdu 4442 Physical Examination (2012年金華賽區現場賽A題)

昨天模擬賽的時候坑了好久，剛開始感覺是dp，仔細一看數據范圍太大。

題目大意：一個人要參加考試，一共有n個科目，每個科目都有一個相應的隊列，完成這門科目的總時間為a+b*（前面已完成科目所花的總時間）。問：怎樣安排考試的順序使考完所花的總時間最短。

分析：假設已經花了time時間，在剩下的科目中任意取兩個科目x，y。

? ? ? ? 先考試x:Tx=time+(ay*time+ax+bx*by*(ax+time))；

? ? ? ? 先考試y:Ty=time+(by*time+bx+ax+ay*(bx+time))。

化簡之后發現花費時間的差距在ax*by，ay*bx，那么按照ai/bi的大小進行排序就ok了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 #define N 100010
 6 #define INF 0xffffffff
 7 #define MOD (365*24*60*60)
 8 
 9 struct node
10 {
11     __int64 a, b;
12     double s;
13 };
14 node stu[N];
15 
16 int cmp (const void *a, const void *b)
17 {
18     node *c = (node *)a;
19     node *d = (node *)b;
20     
21     return c->s > d->s ? 1:-1;
22 }
23 
24 int  main ()
25 {
26     __int64 n, i, sum;
27     
28     while (scanf ("%I64d", &n), n)
29     {
30         for (i=0; i<n; i++)
31         {
32             scanf ("%I64d %I64d", &stu[i].a, &stu[i].b);
33             if (!stu[i].a)
34                 stu[i].s = 0;
35             else if (!stu[i].b)
36                 stu[i].s = INF;
37             else
38                 stu[i].s = 1.0 * stu[i].a / stu[i].b;
39         }
40 
41         qsort (stu, n, sizeof(stu[0]), cmp);
42         sum = 0;
43 
44         for (i=0; i<n; i++)
45         {
46             sum += (stu[i].a + stu[i].b * sum) % MOD;
47             sum %= MOD;
48         }
49 
50         printf ("%I64d\n", sum);
51     }
52 
53     return 0;
54 }

轉載于:https://www.cnblogs.com/alihenaixiao/p/4040659.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/258089.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/258089.shtml
英文地址，請注明出處：http://en.pswp.cn/news/258089.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！