```cpp // https://www.lanqiao.cn/problems/19703/learning/?page=1&first_category_id=1&name=%E8%AE%AD%E7%BB%83%E5%A3%AB%E5%85%B5 #include <bits/stdc++.h> #define N 100010 using namespace std; typedef long long ll; typedef pair<ll, ll> PLL; ll n, S, ans = 0; map<ll, ll, greater<ll>> l; vector<PLL> ps(N); int main() { cin >> n >> S; for (ll i = 0; i < n; i++) { ll p, c; cin >> p >> c; l[c] += p; } ll ii = 0; for (auto i: l) { if (!ii) ps[ii] = {i.first, i.second}; else ps[ii] = {i.first, ps[ii - 1].second + i.second}; ii++; } ll cntS = 0; for (ll i = 0; i < ps.size(); i++) if (ps[i].second >= S) { ans += ps[i].first * S; cntS = ps[i].first; break; } for (ll i = 0; i < ps.size(); i++) if (ps[i].first - cntS <= 0) break; else if (!i) ans += (ps[i].first - cntS) * ps[i].second; else ans += (ps[i].first - cntS) * (ps[i].second - ps[i - 1].second); cout << ans << endl; return 0; } ```

贪心+前缀和 ``` #include<bits/stdc++.h> using namespace std; using ll=long long; const int N=1e5+9; ll n,s,pre[N],ans,tuanti; struct node { ll p,c; bool operator<(const node &i)const { return c<i.c; } }a[N]; int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>s; for(int i=1;i<=n;i++)cin>>a[i].p>>a[i].c; sort(a+1,a+1+n); for(int i=n;i>=1;i--)pre[i]=pre[i+1]+a[i].p; //for(int i=1;i<=n;i++)cout<<pre[i]<<' ';cout<<'\n'; for(int i=1;i<=n;i++) { if(tuanti==a[i].c)continue; if(s<=pre[i]) { ans+=(a[i].c-tuanti)*s; tuanti=a[i].c; }else if(s>pre[i]) { ans+=(a[i].c-tuanti)*a[i].p; //tuanti=a[i].c; } } cout<<ans<<'\n'; return 0; } /*Ac */ ```