P9692题解

what_could_I_do · 2023-10-04 10:28:25 · 题解

传送门

很明显的贪心。

我们需要用尽可能少的价钱买下尽可能多的物品并用尽可能多的价钱卖出。

所以我们要先对题目给的序列进行排序，接下来用 i 和 j 表示序列的头尾两端，然后如果 i 的交易次数比 j 多，那么卖出的物品数量就是 j 的次数，让 j 减 1。如果 j 的交易次数比 i 多，那么卖出的物品数量就是 i 的次数，i 加 1。如果 i 的价格已经与 j 相同，就没必要交易了，退出。

CODE:

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
struct aaa
{
    long long a,b;
}c[100010];
inline bool cmp(aaa x,aaa y)
{
    return x.a<y.a;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        long long ans=0;
        scanf("%d",&n);
        for(register int i=1;i<=n;i++) scanf("%lld%lld",&c[i].a,&c[i].b);
        sort(c+1,c+n+1,cmp);
        int j=1,k=n;
        while(1)
        {
            if(c[j].a==c[k].a) break;
            if(c[j].b>c[k].b) ans+=(c[k].a-c[j].a)*c[k].b,c[j].b-=c[k].b,k--;
            else ans+=(c[k].a-c[j].a)*c[j].b,c[k].b-=c[j].b,j++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}