首页 > 代码库 > 【VIJOS】P1401复制CS
【VIJOS】P1401复制CS
背景
SQ CLASS的机房里流行玩CS,几乎每台电脑上的D盘都有(每台电脑只有C盘和D盘,C盘有硬盘保护卡保护)。SQ非常恼火,因为这严重影响了教学秩序。
描述
有一天,机房所有机器的D盘都被物理格式化了,也就是说CS全都没有了;而且局域网也被关闭了,也就是说网上邻居看不到其他机器了。
但是,道高一尺,魔高一丈。一天,一个同学不知道使用了什么方法,在一台计算机的D盘上安装了CS。由于局域网不通了,其他同学没有办法通过网络复制。但是,现在有k根并口线,可以用来复制。一根并口线可以连接两台计算机;一台计算机只有一个并口,因此同一时刻只能连一根并口线。两台计算机如果用并口线连接了,就可以进行复制,但由于并口的传输速率较慢,所以复制一次CS要一个小时。
需要注意的是:由于SQ对CS的深恶痛绝,他和他的助教将进行不定期的视察,次数为M视察期间并口线上不能传输数据,原来没有传完的CS也将遭到灭顶之灾。万幸的是,同学们获取了老师视察的时间总表。
现在有n个同学要玩CS,开始时只有一台机器上有CS。使用这k根并口线,在其他的n-1台计算机上都装上CS。同学们希望尽快能一起玩,你能计算一下至少需要多少小时吗?
(SQ:何时CS才能从机房消失?玩CS,以后可有的是时间啊!)
格式
输入格式
N,k和M的值,中间以一个空格分开。(2≤n≤10E9, 1≤k≤10E9, 1≤M≤10E3)
以下M行有A和B两个值,A代表视察开始的时间(小时),B代表视察持续的时间(小时)。
输出格式
一个整数,表示n台计算机上都复制好CS至少需要多少小时。(保留两位小数)
样例1
样例输入1[复制]
8 3 21.1 0.94 1
样例输出1[复制]
6.00
限制
1 second
提示
一开始有一台已经装好。第0到1小时复制出1台,一共2台有了。第1到1.1小时,复制中。第1.1到2小时,老师视察。第2到3小时,两台可以同时又复制出两台。第3-4小时,由于只有3根并口线,所以只能在复制出3台,一共7台好了。所以还需要一个小时(5.0-6.0)。
来源
SQ CLASS公开编程竞赛2008——Problem A
Source: SQ, liuichou, royZhang
题解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int MAXN = 1001; struct MyStruct { double l, r; }a[MAXN],tls[MAXN]; bool operator<(MyStruct a, MyStruct b) { if (a.l == b.l) return a.r < b.r; return a.l < b.l; } int n, m, k; int main( int argc, char *argv[]) { int i, j, cnt=1; scanf ( "%d%d%d" , &n, &k, &m); for (i = 1; i <= m; i++) { scanf ( "%lf%lf" , &a[i].l, &a[i].r); a[i].r += a[i].l; //a[i].l = (int)a[i].l; //a[i].r = (int)a[i].r + 1; } sort(a + 1, a + m + 1); tls[1] = a[1]; for ( i = 2; i <= m; i++) { if (a[i].l <= tls[cnt].r) { tls[cnt].l = min(tls[cnt].l, a[i].l); tls[cnt].r = max(tls[cnt].r, a[i].r); } else { cnt++; tls[cnt].l = a[i].l; tls[cnt].r = a[i].r; } } //for (i = 1; i <= cnt; i++) //cout << tls[i].l << ‘ ‘ << tls[i].r << endl; int now = 0; double maxi = 0,ans=0; int num_copy = 1; i = 1; bool flag = false ; while (now <= n) { int len = ( int )(tls[i].l - ans); for (j = 1; j <= len; j++) { now += num_copy; num_copy *= 2; if (num_copy > k) num_copy = k; ans++; if (now >= n) { flag = true ; break ; } } if (flag == true ) break ; ans = max(ans, tls[i].r); i++; if (i > cnt) { while (now <= n) { now += num_copy; num_copy *= 2; if (num_copy > k) num_copy = k; ans++; } } } printf ( "%.2f\n" , ans); return 0; } |
【VIJOS】P1401复制CS