专栏文章

题解：P11376 [GESP202412 六级] 运送物资

BBh_hurter
P11376题解参与者 2已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqt7ryc
此快照首次捕获于
2025/12/04 10:21
3 个月前
此快照最后确认于
2025/12/04 10:21
3 个月前
查看原文

P11376 题解

题目传送门

题意分析

题意很简单，要把 mm 辆车放到 nn 个车站中，其中每个车站 pp 在 pip_i 的位置，可以存下 cic_i 辆车。目标是找到一种方案，使得所有的车送完物资后总行驶里程最小。
不难想到，一辆车每往 AA 地和 BB 地各送一次物资，路程 S=2×p+2×(x−p)=2×(p+x−p)=2×xS=2 \times p+2 \times (x-p) =2 \times (p+x-p) =2 \times x ，即走了两趟全程。所以不管这辆车的起始站在哪里，每往 AA 地和 BB 地各送一次物资，路程都是 22 倍的全程。
不免想到贪心。既然一辆车每往 AA 地和 BB 地各送一次物资，路程都是 22 倍的全程，那么这辆车至少会走 ai a_i 和 bib_i 中较小的那个倍数的全程。所以只用考虑 aia_i 或 bib_i 多出来的部分就行了。
先把所有站点排个序，然后将 aia_i 大的车从离 AA 地最近的站点开始放，每次先放当前 ai−bia_i-b_i 最大的车。同样从离 BB 地最近的车站开始放 bib_i 大的车，每次先放当前 bi−aib_i-a_i 最大的车。可以在输入时将这两种车分开存，处理更加方便。

AC Code

下面是本人考场代码，给大家献丑了。
CPP
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
const int N=1e5;
struct node {
	int a,b;
}cara[N+5],carb[N+5];//cara存a[i]较大的车，carb存b[i]较大的车
struct point {
	int p,c;
}st[N+5];//每个车站信息
int n,m,px;
int cnta=0,cntb=0;
ll ans=0;
bool cmp(node x,node y) {
	return abs(x.a-x.b)<abs(y.a-y.b);
}
bool cmq(point x,point y) {
	return x.p<y.p;
}
int main() {
	cin>>n>>m>>px;
	for(int i=1; i<=n; i++) {
		cin>>st[i].p>>st[i].c;
	}
	sort(st+1,st+1+n,cmq);
	for(int i=1; i<=m; i++) {
		int x,y;
		cin>>x>>y;
		if(x>=y) cara[++cnta].a=x,cara[cnta].b=y;
		else carb[++cntb].a=x,carb[cntb].b=y;
	}
	sort(cara+1,cara+1+cnta,cmp);//采用倒着排序，后面每次放完一辆车后只需cnta--便可删除这个车
	sort(carb+1,carb+1+cntb,cmp);//同理
	int l=1,r=n;
	while(cnta>0) {
		if(cnta<st[l].c) {//小心下表越界
			while(cnta>0) {
				ans=ans+2ll*cara[cnta].a*st[l].p+2ll*cara[cnta].b*(px-st[l].p);
				cnta--;//放完这辆车了，删掉
			}
		} else {
			for(int i=1; i<=st[l].c; i++) {
				ans=ans+2ll*cara[cnta].a*st[l].p+2ll*cara[cnta].b*(px-st[l].p);//计算答案
				cnta--;//放完这辆车了，删掉
			}
			l++;//下一车站
		}
	}
	while(cntb>0) {
		if(cntb<st[r].c) {//小心下表越界
			while(cntb>0) {
				ans=ans+2ll*carb[cntb].a*st[r].p+2ll*carb[cntb].b*(px-st[r].p);
				cntb--;//放完这辆车了，删掉
			}
		} else {
			for(int i=1; i<=st[r].c; i++) {
				ans=ans+2ll*carb[cntb].a*st[r].p+2ll*carb[cntb].b*(px-st[r].p);//计算答案
				cntb--;//放完这辆车了，删掉
			}
			r--;//下一车站
		}

	}
	cout<<ans;//输出
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...