北京建站模板公司,公司网站宣传设计,网站外链数怎么查,郑州微信公众号网站建设昨天模拟赛的时候坑了好久#xff0c;刚开始感觉是dp#xff0c;仔细一看数据范围太大。 题目大意#xff1a;一个人要参加考试#xff0c;一共有n个科目#xff0c;每个科目都有一个相应的队列#xff0c;完成这门科目的总时间为ab*#xff08;前面已完成科目所花的总时…昨天模拟赛的时候坑了好久刚开始感觉是dp仔细一看数据范围太大。 题目大意一个人要参加考试一共有n个科目每个科目都有一个相应的队列完成这门科目的总时间为ab*前面已完成科目所花的总时间。问怎样安排考试的顺序使考完所花的总时间最短。 分析假设已经花了time时间在剩下的科目中任意取两个科目xy。 先考试x:Txtime(ay*timeaxbx*by*(axtime)) 先考试y:Tytime(by*timebxaxay*(bxtime))。 化简之后发现花费时间的差距在ax*byay*bx那么按照ai/bi的大小进行排序就ok了。 1 #include stdio.h2 #include string.h3 #include stdlib.h4 5 #define N 1000106 #define INF 0xffffffff7 #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 (i0; in; 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 (i0; in; 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
