P8837 [传智杯 #3 决赛] 商店 题解

· · 题解

一道简单的橙题

思路很简单，贪心+排序。

我们令 m 件商品和 n 名同学依次按价格和财力进行排序，让同学们依次来选购商品，如果买的走，就买走它，再接着卖下一件商品；如果钱不够，则让下一个人来选购。

用两个变量分别指向轮到第几个人买和该卖第几样东西，再输出有几个人买到了东西即可。

不多说了，代码里有注释：

#include<iostream>
#include<algorithm> 
using namespace std;
int n,m,a[100005],b[100005],cnt,zz1=1,zz2=1;//zz1,zz2分别指向轮到第几个人买东西和该卖第几样东西
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    sort(a+1,a+n+1);//对人们的钱数排序 
    sort(b+1,b+m+1);//对商品的价格排序 
    while(zz1<=n&&zz2<=m){//还有人没开始买且商品还没卖完
        if(a[zz1]>=b[zz2]){//买的起 
            cnt++;//多了一个买得起商品的人
            zz1++;//下一个人来买 
            zz2++;//卖下一件商品 
        }
        else zz1++;//买不起就下一个人来买 
    }
    cout<<cnt; 
    return 0;
}
\mathbb{---END---}