2024-12 · 6级 · 运送物资

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1350 字

CCF 原卷官方标程 · 数组与向量、STL、位运算、贪心 · 本地编译通过

2024-12
数组与向量

正文

// GESP 2024-12 C++ 6级 编程题 2 · 运送物资
// 原题：https://oj.yecheng.tv/p/gs2412l6p2
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1733580036243488.pdf
// 题意：小杨管理着辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。
// 知识点：数组与向量、STL、位运算、贪心
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 1/1 通过
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int n,m;
ll x;
vector<pair<int,int> > 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(make_pair(p,c));
    }
    sort(st.begin(),st.end());
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
    }
    vector<pair<int,int> > neg,pos;
    ll res=0;
    for(int i=1;i<=m;i++){
        if(a[i]>=b[i])
            pos.push_back(make_pair(a[i]-b[i],i));
        else{
            neg.push_back(make_pair(a[i]-b[i],i));
        }
        res+=1ll*b[i]*x;
    }
    sort(neg.begin(),neg.end());
    sort(pos.begin(),pos.end());
    reverse(pos.begin(),pos.end());
    int l=0,r=n-1;
    for(auto i:neg){
        while(r>=1&&st[r].second==0)r--;
        res+=1ll*(a[i.second]-b[i.second])*st[r].first;
        st[r].second-=1;
    }
    for(auto i:pos){
        while(l<=n&&st[l].second==0)l++;
        res+=1ll*(a[i.second]-b[i.second])*st[l].first;
        st[l].second-=1;
    }
    cout<<res*2<<"\n";
}

2024-12 · 6级 · 运送物资

正文

GESP 标程 · 考级真题的其它内容