「RCOI2019」Rochine Round 1 T2解析
引领天下
2019-12-09 20:57:19
这个题的 idea 其实很早以前就有了，但是由于某团的特性一直到现在才与大家见面
题意我就不复述了，直接谈做法
这个题首先给人不舒服的地方就是在于这个环形跑道不准超车，这就导致如果安排不当的话是完全可以造成堵车的。那么怎么解决这个问题呢？
一个神奇的思想出现了：
**把所有车和货物全部拉到 $\mathbf{0}$ 号点！**
那么，一个 $t$ 时刻在 $i$ 位置出现的货物实际上等价于一个 $t-i$ 时刻在 $0$ 位置 出现的货物。
接下来的事情就很简单啦，我们对当前的小车建立一个小根堆，初始是 $m$ 个 $0$，然后对货物按拉到 $0$ 位置之后出现的时间排序，派出当前空闲的最靠前的小车去接，接完之后将小车跑一圈回来到达 $0$ 位置的时间重新 push 进小车的堆即可。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,num,a[10000005];
priority_queue<long long,vector<long long>,greater<long long>>q;//小车的堆
struct control{
int ct,val;
control(int Ct,int Val=-1):ct(Ct),val(Val){}
inline control operator()(int Val){return control(ct,Val);}
}_endl(0),_prs(1),_setprecision(2);
struct FastIO{
#define IOSIZE 1000000
char in[IOSIZE],*p,*pp,out[IOSIZE],*q,*qq,ch[20],*t,b,K,prs;
FastIO():p(in),pp(in),q(out),qq(out+IOSIZE),t(ch),b(1),K(6){}
~FastIO(){fwrite(out,1,q-out,stdout);}
inline char getch(){return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?b=0,EOF:*p++;}
inline void putch(char x){q==qq&&(fwrite(out,1,q-out,stdout),q=out),*q++=x;}
inline void puts(const char str[]){fwrite(out,1,q-out,stdout),fwrite(str,1,strlen(str),stdout),q=out;}
inline void getline(string&s){
s="";
for(register char ch;(ch=getch())!='\n'&&b;)s+=ch;
}
#define indef(T)inline FastIO&operator>>(T&x)\
{\
x=0;register char f=0,ch;\
while(!isdigit(ch=getch())&&b)f|=ch=='-';\
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getch();\
return x=f?-x:x,*this;\
}
indef(int)
indef(long long)
inline FastIO&operator>>(char&ch){return ch=getch(),*this;}
inline FastIO&operator>>(string&s){
s="";
register char ch;
while(isspace(ch=getch())&&b);
while(!isspace(ch)&&b)s+=ch,ch=getch();
return*this;
}
inline FastIO&operator>>(double&x){
x=0;
register char f=0,ch;
double d=0.1;
while(!isdigit(ch=getch())&&b)f|=(ch=='-');
while(isdigit(ch))x=x*10+(ch^48),ch=getch();
if(ch=='.')while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1;
return x=f?-x:x,*this;
}
#define outdef(_T)inline FastIO&operator<<(_T x)\
{\
!x&&(putch('0'),0),x<0&&(putch('-'),x=-x);\
while(x)*t++=x%10+48,x/=10;\
while(t!=ch)*q++=*--t;\
return*this;\
}
outdef(int)
outdef(long long)
inline FastIO&operator<<(char ch){return putch(ch),*this;}
inline FastIO&operator<<(const char str[]){return puts(str),*this;}
inline FastIO&operator<<(const string&s){return puts(s.c_str()),*this;}
inline FastIO&operator<<(double x){
register int k=0;
this->operator<<(int(x));
putch('.');
x-=int(x);
prs&&(x+=5*pow(10,-K-1));
while(k<K)putch(int(x*=10)^48),x-=int(x),++k;
return*this;
}
inline FastIO&operator<<(const control&cl){
switch(cl.ct){
case 0:putch('\n');break;
case 1:prs=cl.val;break;
case 2:K=cl.val;break;
}
}
inline operator bool(){return b;}
}io;//快读
int main(){
io>>n>>m;
for(long long i=1;i<=n;i++){
for(io>>k;k;k--){
num++;
io>>a[num];
a[num]-=i;//读入的同时就把货物拉到0位置，出现的时间-=小车跑到货物原始位置的时间（即货物原始位置）
}
}
sort(a+1,a+num+1);//对拉到0位置之后的货物按时间排序
for(long long i=1;i<=m;i++)q.push(0);//丢m个0（每个小车初始的最早可出发时间都为0）
for(long long i=1;i<=num;i++){
long long t=q.top();//取出堆顶的车，pop掉
q.pop();
q.push(max(t,a[i])+n+1);//车能出发的时间要和货物出现的时间取max
}
while(q.size()>1)q.pop();//最后堆中剩下的可出发时间最迟的小车即为答案
io<<q.top();
return 0;
}
```
#### 关于本题
- 出题人太菜了，本来花0.5h想了个分类讨论的dp，打算实现的时候发现太麻烦了于是去找Sooke，Sooke神仙花了10min给出了题解中这个做法并爆踩了标算。（Sooke太强辣！）
- 本题的卡常并不是我一个人决定的（大雾，我当时要调时限的时候Karry5307坚决反对（企图甩锅）
为此，作者还受到了神虎的强烈谴责
~~我太难了~~