1 条题解
-
2
这是一道模拟题。
考虑到可以按起点位置排序后,每到一个货仓时先卸载所有完成运输的点,若没装满,则装当前货仓的货物直到装满。然后若有货物目的地比当前装在车里的货物目的地靠前,则替换。
由于数据范围极小,可以直接用 priority_queue 维护。
为防止在同一货仓反复发生替换,考虑以目标位置降序为第二关键字排序。
在运输完后,我们不用去删队列中的货物,因为肯定无法在后续的操作中替换这些货物,仅需减小当前装的的数量(相当于放下这些货物)即可。
code(写的有点史):
#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; int n,m,k,b[N],now=1,noww=0,ans=0; //now:第几批货物,noww:当前装了几件货物 //b_i:装了多少目的地为 i 的货物 struct node{ int a,b,t; }; node a[N]; bool cmp(node a,node b){ if(a.a!=b.a) return a.a<b.a;//以起点位置为第一关键字 return a.b<b.b;//以目标位置为第二关键字(原因见上) } priority_queue<int> pq;//优先队列 signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>k>>n>>m;//注意顺序 for(int i=1;i<=k;i++){ cin>>a[i].a>>a[i].b>>a[i].t; } sort(a+1,a+k+1,cmp); for(int i=1;i<=n;i++){ ans+=b[i];//累加运输完成的货物的数量 noww-=b[i];//等价于放下所有运输完成的货物 while(now<=k&&a[now].a==i){//遍历当前位置所有货物 while(a[now].t>0&&noww<=m){//如果还有空 if(noww==m) break; noww++;//货物数++ a[now].t--;//当前批次货物数量-- pq.push(a[now].b);//目标位置加入优先队列 b[a[now].b]++;//目标为a[now].b的货物数++ } while(a[now].t>0&&a[now].b<pq.top()){ //如果当前批次货物的目标位置 < 装的最大的目标位置 b[pq.top()]--;//目标为pq.top()的货物数-- pq.pop();//扔掉这件货物 pq.push(a[now].b);//讲这个货物加入队列 a[now].t--;//当前批次货物数量-- b[a[now].b]++;//目标为a[now].b的货物数++ } now++; } } cout<<ans; return 0; }由于每个货仓最多只能发生 次替换,因此时间复杂度为:
似乎可以加强数据,那样就过不了了。
信息
- ID
- 942
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 38
- 已通过
- 10
- 上传者