【CodeForces】779C - Dishonest Sellers（贪心）

FishWang

发布于 2025-08-26 20:46:06

5100

代码可运行

运行总次数：0

代码可运行

题目链接：这里写链接内容

题意：给出n个物品，分别给出起始价格和促销后价格（促销后的有可能更贵），但是要求打折前至少买k件物品。最后计算买完所有物品最少需要多少钱。

题解：主要还是一个贪心策略，我们考虑到每个物品肯定是要买的，所以它打折前和打折后的价格和同时期的物品比较是没有意义的，我们需要的是他打折后省了多少钱（有可能浪费了钱）。所以我们计算出每一个物品打折后省了多少钱，如果是浪费钱了，那我们肯定在打折前就买（不亏不赚的也买，占k的数值），如果最后的总数没有大于k，那么我们就先吧赚的少的买了，这样亏的就少。

代码如下：

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
#define LL long long
struct node
{
    int pr,ne;
    int cost;
}data[200000+5];
bool cmp(node a,node b)
{
    return a.cost < b.cost;
}
int main()
{
    int n,k;
    __int64 sum = 0;
    scanf ("%d %d",&n,&k);
    for (int i = 0 ; i < n ; i++)
        scanf ("%d",&data[i].pr);

    int ant = 0;
    for (int i = 0 ; i < n ; i++)
    {
        scanf ("%d",&data[i].ne);
        sum += data[i].ne;
        data[i].cost = data[i].pr - data[i].ne;
        if (data[i].cost <= 0)
            ant++;
    }
    sort(data,data+n,cmp);
    if (ant >= k)
    {
        for (int i = 0 ; i < n ; i++)
        {
            if (data[i].cost < 0)
                sum += data[i].cost;
            if (data[i].cost >= 0)
                break;
        }
        printf ("%I64d\n",sum);
    }
    else
    {
        for (int i = 0 ; i < k ; i++)
            sum += data[i].cost;
        printf ("%I64d\n",sum);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

include