题解P2983

· · 题解

纯贪心+结构体排序

一开始我还以为是背包，自从看到了10^18

没用int64之类，而是unsigned long long（代码如下）

#include<iostream>
#include<algorithm>
using namespace std;//正常
int n;
unsigned long long ans,v;
struct cz{
    unsigned long long p,c;
}a[100005];//全部开unsigned long long
bool cmp(cz x,cz y){return x.p<y.p;}//结构体排序必要的cmp QAQ
int main(){
    cin>>n>>v;
    for(int i=1;i<=n;i++)cin>>a[i].p>>a[i].c;//表示不会用scanf（unsigned long long）
    sort(a+1,a+n+1,cmp);//结构体排序
    for(int i=1;i<=n;i++){//贪心ing
        if(v>a[i].p*a[i].c){v=v-a[i].p*a[i].c;ans+=a[i].c;}//能让第i种奶牛全部高兴就高兴
        else{ans+=v/a[i].p;break;}//不能了就尽量是奶牛高兴
    }
    cout<<ans;
    return 0;
}

SEE YOU! （蒟蒻的第一篇题解，求过QAQ）