首页 > 代码库 > 【VIJOS】P1401复制CS

【VIJOS】P1401复制CS

2024-08-15 01:55:11   220人阅读

背景

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

 

题解：
  题目名挺好玩的……离散化+模拟（居然自己YY的两发就A了）模拟水平已经差到一定程度了……
  大约就是找出老师的巡查间隔作为连续的区间……重叠的部分直接预处理的时候离散化一下就ok
  然后就是注意各种细节，比如巡查完成后没跳出循环什么的……还有转int的时候什么的（离散化之前我转了int就水了1个点）
  模拟的题还是要想清细节啊
 
?
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


联系
我们