首页 > 代码库 > Codeforces Round #402 (Div. 2) C. Dishonest Sellers

Codeforces Round #402 (Div. 2) C. Dishonest Sellers

题目链接:Codeforces Round #402 (Div. 2) C. Dishonest Sellers

题意:

有n个商品,每个商品这一周为ai的价格,下一周为bi的价格。

现在那个人要将这n个商品全部买掉,这一周最少要买k个商品,

为最小的花费是多少。

题解:

xjb贪心一下。

按ai-bi排序,为负的要全部买掉,然后如果小于k件,就买前k件。

最后再买下一周的。

技术分享
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=2e5+7;
 6 int n,k;
 7 struct dt
 8 {
 9     int a,b,v;
10     bool operator <(const dt &b)const
11     {
12         return v==b.v?a<b.a:v<b.v;
13     }
14 }a[N];
15 
16 int main(){
17     scanf("%d%d",&n,&k);
18     F(i,1,n)scanf("%d",&a[i].a);
19     F(i,1,n)
20     {
21         scanf("%d",&a[i].b);
22         a[i].v=a[i].a-a[i].b;
23     }
24     sort(a+1,a+1+n);
25     int ans=0,i;
26     for(i=1;i<=n;i++)
27     {
28         if(i-1>=k&&a[i].v>0)break;
29         ans+=a[i].a;
30     }
31     for(;i<=n;i++)ans+=a[i].b;
32     printf("%d\n",ans);
33     return 0;
34 }
View Code

 

Codeforces Round #402 (Div. 2) C. Dishonest Sellers