首页 > 代码库 > CodeForces 779C Dishonest Sellers

CodeForces 779C Dishonest Sellers

贪心。

如果这周便宜,那么肯定这周买。另外要求这周至少买到$k$个,那么肯定是需要额外购买差价小的。

#include<map>#include<set>#include<ctime>#include<cmath>#include<queue>#include<string>#include<vector>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<functional>using namespace std;int n,k;int a[200010], b[200010],f[200010],sum;struct X{    int a,b;}s[200010];bool cmp(X a,X b){    return a.a-a.b<b.a-b.b;}int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++) scanf("%d",&a[i]);    for(int i=1;i<=n;i++) scanf("%d",&b[i]);    int ans=0;    for(int i=1;i<=n;i++)    {        if(a[i]<=b[i]) ans=ans+a[i],f[i]=1, sum++;    }    if(sum>=k)    {        for(int i=1;i<=n;i++)        {            if(f[i]) continue;            ans=ans+b[i];        }    }    else    {        int sz=0;        for(int i=1;i<=n;i++)        {            if(f[i]) continue;            s[sz].a =a[i];            s[sz].b = b[i];            sz++;        }        sort(s,s+sz,cmp);        int y = 0;        for(int i=0;i<sz;i++)        {            if(y<k-sum) ans=ans+s[i].a;            else ans=ans+s[i].b;            y++;        }    }    printf("%d\n",ans);    return 0;}

 

CodeForces 779C Dishonest Sellers