每日一题 购物 (优先队列)

一.题意

有 天，每天可购买 个糖，不同时间、不同的糖有不同价格。
每天购买 个糖有额外代价 。
第 天结束时累计购买数达到 。
求最小花费。

二.题解

参考一个题解： https://blog.nowcoder.net/n/aec8d532559a4fc4bd1561da0ec16848

用一个小根堆维护糖果的代价，但是考虑到有一个额外的代价，所以会比较麻烦。
而把所有糖果排序后再加上额外的代价就可以用小根堆轻松实现。
因为如果单独考虑在某一天买 k 个糖果，即使有额外代价，在该天买 k 个糖果的最优策略仍然是选代价最小，那么该天买糖果的顺序其实是固定的，这样一来不妨直接把额外代价算进糖果本身的代价中。

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e5+5;
const int N=2e3+5;
const int mod=1e9+7;

priority_queue<ll,vector<ll>,greater<ll> >q;
ll a[N][N];
int main(){
    io; ll m,n; cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            cin>>a[i][j];
    for(int i=1;i<=n;i++) sort(a[i]+1,a[i]+1+m);
    for(int i=1;i<=n;i++){
        ll x=1;
        for(int j=1;j<=m;j++)
            a[i][j]+=x,x+=2;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            q.push(a[i][j]);
        }
        ans+=q.top(); q.pop();
    }
    cout<<ans;
    return 0;
}