1 solutions

  • 1
    @ 2025-8-27 10:38:02
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef pair<int,int> PII;
    const int N=1e5+10;
    int n,m,x;
    vector<PII> st;
    int a[N],b[N];
    int main()
    {
    	cin>>n>>m>>x;
    	for(int i=1;i<=n;i++)
    	{
    		int p,c;
    		cin>>p>>c;
    		st.push_back({p,c}); //站点位置和车辆数目
    	}
    	sort(st.begin(),st.end()); //按照位置排序
    	for(int i=1;i<=m;i++) //左边和右边的数量
    	{
    		cin>>a[i]>>b[i];
    	}
    	vector<PII> right,left;
    	LL res=0;
    	for(int i=1;i<=m;i++)//枚举货车
    	{
    		if(a[i]>=b[i]) //优先去前面(p)
    		{
    			left.push_back({a[i]-b[i],i});
    		}
    		else //优先去后面(x-p)
    		{
    			right.push_back({a[i]-b[i],i});
    		}
    		res+=1LL*b[i]*x; //计算
    	}
    	sort(right.begin(),right.end()); //从小到大排序
    	sort(left.begin(),left.end()); //从小到大排序
    	reverse(left.begin(),left.end()); //从大到小排序
    	int l=0,r=n-1; //站点的起点和终点
    	for(auto i:right) //后面
    	{
    		while(r>=1&&st[r].second==0) r--; //找到后面第一个非0的位置
    		res+=1ll*(a[i.second]-b[i.second])*st[r].first; //减去到前面的距离
    		st[r].second-=1; //这个站点少了一辆车子
    	}
    	for(auto i:left) //前面
    	{
    		while(l<=n&&st[l].second==0) l++; //找到前面的第一个非0的位置
    		res+=1ll*(a[i.second]-b[i.second])*st[l].first; //累加前面的距离
    		st[l].second-=1;
    	}
    	cout<<res*2; //来回距离
    	return 0;
    }
    

    Information

    ID
    2220
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    2
    Accepted
    2
    Uploaded By