酷暑一夏1

不忘初心,方得始终


Vijos1401 复制CS题解

题目

初始时只有1台电脑上装有CS,你有$K$根串口线,只能通过串口线传输数据,一根串口线只能连接两台电脑,每台电脑只有1个串口接口,每次复制需要1小时,且在一定时间段内不得复制,之前的复制也将被中断,求复制完所需的最小时间。

题解

题目很简单,对于每段时间(0~第一次视察,每次视察间的空隙,最后一次视察~∞),直接计算这段时间可以传多少份CS即可,传够了就停,但是要注意在k根线没有全部用上时,每次可以传输的电脑数是可变的。
坑点很多,一一解决。

  1. 视察时间并不是排好序的,因此你需要排个序
  2. 视察的时间彼此有可能相交,因此要合并相交的。相交的话,如下图所示,对于两段时间$i,j$只要$end_i>start_j$并且$start_i<start_j$即可判为相交。
    123567e711a.jpg

代码

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
#include<cstdio>
#include<algorithm>
const int MAXN=1000+5;
struct data{double start,keep,end;};
int hascs=1,k,n,m,totuse;double now,start,keep;data d[MAXN];bool used[MAXN];
bool comp(data a,data b){return a.start+a.keep<b.start+b.keep;}
int main()
{
scanf("%d %d %d",&n,&k,&m);
for(int i=1;i<=m;i++)
{
scanf("%lf %lf",&d[i].start,&d[i].keep);
d[i].end=d[i].start+d[i].keep;
}
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
{
if((d[i].start<d[j].start && d[i].start+d[i].keep>d[j].start))
{
d[i].start=d[j].start=std::min(d[i].start,d[j].start);
d[i].keep=d[j].keep=std::max(d[j].end,d[i].end)-d[i].start;
d[i].end=d[j].end=d[i].start+d[i].keep;
}
}
std::sort(d+1,d+m+1,comp);
// printf("%d",m);
for(int i=1;i<=m;i++)
{
start=d[i].start;keep=d[i].keep;
for(;now+1<=start;now++)
{
// printf("Copied %d new cses,it's %.2lf now\n",std::min(hascs,k),now+1);
hascs+=std::min(hascs,k);
if(hascs>=n)
{
printf("%.2lf",now+1);
return 0;
}
}
now=start+keep;
// printf("TIME=%.2lf\n",now);
}
for(;hascs<n;now++)
{
// printf("Copied %d new cses,it's %.2lf now\n",std::min(hascs,k),now+1);
hascs+=std::min(hascs,k);
if(hascs>=n)
{
printf("%.2lf",now+1);
return 0;
}
//printf("%d\n",hascs);
}
return 0;
}
最近的文章

牛客练习赛9 A,B,D 题解

A题目珂朵莉想每天都给威廉送礼物,于是她准备了n个自己的本子她想送最多的天数,使得每天至少送一个本子,但是相邻两天送的本子个数不能相同珂朵莉最多送几天礼物呢 题解很明显,符合要求的最小整数有1和2,只要1,2,1,2,1,2,…这样算下去就好了 代码1234567891011121314151617 …

于  NowCoder, 比赛, 牛客练习赛 继续阅读
更早的文章

CodeVS1160 蛇形矩阵 题解

题目小明玩一个数字游戏,取个n行n列数字矩阵(其中n为不超过100的奇数),数字的填补方法为:在矩阵中心从1开始以逆时针方向绕行,逐圈扩大,直到n行n列填满数字,请输出该n行n列正方形矩阵以及其的对角线数字之和. 题解蛇形矩阵生成见GIF,从$(n,n)$开始每一圈按照左-&gt;上-&gt;右-& …

于  CodeVS 继续阅读