Strange Birthday Party CodeForces - 1471C

Strange Birthday Party CodeForces - 1471C

题意：

我有n个朋友，商店有m种商品，这m种商品按序号价格从小到大排列，对于每一个朋友我给出一个序号k，我可以直接给朋友序号k的商品价格的金钱或给朋友买一个序号小于k的商品，且每种商品最多只能买一次，问我需要花费的最少金钱？

题解：

简单的贪心
我们将朋友的序号从大到小排序
因为商品价值从小往大，由题意序号大的商品花费的金钱一定大于等于序号小的，所以我们只需要让序号大的朋友优先选用前面序号小的商品替代使花费金钱减少，直到前面的商品都已经被买了一次，然后后面的朋友直接给出对应序号金钱即可。

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=3e5+9;
int k[maxn],c[maxn];
struct node{
    int u,v,w,next;
}edge[maxn];
int cnt,head[maxn];
void add(int u,int v,int w)
{
    edge[++cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>k[i];
        for(int i=1;i<=m;i++)cin>>c[i];
        sort(k+1,k+1+n,greater<int>());
        ll sum=0;
        int d=1;
        for(int i=1;i<=n;i++)
        {
            if(k[i]>=d)sum+=c[d++];
            else sum+=c[k[i]];
        }
        cout<<sum<<endl;
    }
}