贪心+前缀和
#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
*/
1 回复
0 转发
0 喜欢
2 阅读



