P9556 [SDCPC2023] Orders题解

· · 题解

蒟蒻的第一篇题解

拿到这题，我的想法就是模拟+贪心，用一个变量存储已经做过的订单，显而易见，我们应该先做截止日期较前的订单，那么怎么算该天剩余多少货呢？我们要开一个变量，记录已完成的货物数，设截止日期为 i，已经做过的件数为 y，那么，第 i 天时，剩余的货物数为

i\times k-y

件（ k 如题中所示）只需要拿这个数和当前订单的货物数对比就行了。

AC code

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
struct dingdan{//每一个订单的信息
    int a,b;
};
int T;
bool cmp(dingdan x,dingdan y){
    return x.a<y.a;
}//根据截止日期排序
dingdan x[101];
void slove(){
    int n,k,tun=0;//tun代表已经做完的件数
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>x[i].a>>x[i].b;
    }
    sort(x+1,x+1+n,cmp);
    for(int i=1;i<=n;i++){
        int tmp=x[i].a*k-tun;//计算还剩多少件
        if(x[i].b<=tmp){//判断是否能做
            tun+=x[i].b;
        }
        else{
            cout<<"No"<<endl;
            return;
        }
    }
    cout<<"Yes"<<endl;
}
signed main(){
    cin>>T;
    while(T--){
        slove();
    }
}