1 条题解

  • 2
    @ 2026-10-26 15:28:07

    这是一道模拟题。

    考虑到可以按起点位置排序后,每到一个货仓时先卸载所有完成运输的点,若没装满,则装当前货仓的货物直到装满。然后若有货物目的地比当前装在车里的货物目的地靠前,则替换。

    由于数据范围极小,可以直接用 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;
    }
    

    由于每个货仓最多只能发生 mm 次替换,因此时间复杂度为:

    O(klog⁡k+n×mlog⁡(n×m))。O\bigl(k\log k+n\times m\log(n\times m)\bigr)。

    似乎可以加强数据,那样就过不了了。

    信息

    ID
    942
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    38
    已通过
    10
    上传者