20分求调
查看原帖
20分求调
152944
lou9527楼主2024/12/14 14:31
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{
	int p,c;
};
struct node2{
	int a,b,dis;
};
node station[N];
node2 car[N];
int n,m,x;
ll ans=0;
bool cmp1(node x,node y){
	return x.p<y.p;
}
bool cmp2(node2 x,node2 y){
	return x.dis>y.dis;
}
int main() {
	cin>>n>>m>>x;
	for(int i=0;i<n;i++){
		cin>>station[i].p>>station[i].c;
	}//输入每个站点的位置和可放置车辆数 
	for(int i=0;i<m;i++){
		cin>>car[i].a>>car[i].b;
		car[i].dis=car[i].a-car[i].b;
	}//输入每辆车向左次数a和向右次数b,并计算dis=a-b 
	sort(station,station+n,cmp1);//站点按位置p从小到大排序 
	sort(car,car+m,cmp2);//车辆按(a-b)从大到小排序
	//因为车辆一定跑min(a,b)个全程,所以dis越大,向左次数越多,dis越小,向右次数越多
	//向左次数多的尽量靠左,向右次数多的尽量靠右 
	int now_pos=0;//初始站点下标 
	for(int i=0;i<m;i++){//枚举m辆车 
		ll dis=0;//当前这辆车需要跑动的距离 
		dis+=(1ll*car[i].a*station[now_pos].p)*2;//加上向左跑动的距离:向左次数a*向左距离p*2 
		dis+=(1ll*car[i].b*(x-station[now_pos].p))*2;//加上向右跑动的距离:向右次数b*向右距离(x-p)*2 
		ans+=dis;//答案变量加上dis 
		station[now_pos].c--;//当前站点可放置车辆数-1 
		if(station[now_pos].c==0){//如果无法放置 
			now_pos++;//去下一个站点 
		}
	}
	cout<<ans<<endl;
	return 0;
}
2024/12/14 14:31
加载中...