WA 116 求调
查看原帖
WA 116 求调
397982
Deuteron楼主2025/1/6 19:38

/kel

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,c;
pair<int,int> f[N],a[N];
int dp[N],v[N];
int s[N],h=1,t;
int cmp(int i,int j,int k){
	int x=(k-v[i]+a[i].first-1)/a[i].first,y=(k-v[j]+a[j].first-1)/a[j].first;
	if(dp[i]+x==dp[j]+y) return v[i]+a[i].first*x<=v[j]+a[j].first*y;
	else return dp[i]+x>dp[j]+y;
}
signed main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>f[i].first>>f[i].second;
	sort(f+1,f+n+1);
	a[0].second=-1;
	for(int i=1;i<=n;i++){
		while(f[i].second<=a[m].second) m--;
		a[++m]=f[i];
	}
	s[++t]=1;
	for(int i=2;i<=m;i++){
		while(h<t&&cmp(s[h],s[h+1],a[i].second)) h++;
		int u=s[h],x=(a[i].second-v[u]+a[u].first-1)/a[u].first;
		dp[i]=dp[u]+x,v[i]=v[u]+a[u].first*x-a[i].second;
		while(h<t&&(a[i].second-a[s[t]].second)*(a[s[t]].first-a[s[t-1]].first)<=(a[s[t]].second-a[s[t-1]].second)*(a[i].first-a[s[t]].first)) t--;
		s[++t]=i;
	}
	int ans=1e18;
	for(int i=1;i<=m;i++) ans=min(ans,dp[i]+max(c-v[i]+a[i].first-1,0ll)/a[i].first);
	cout<<ans<<"\n";
	return 0;
}
2025/1/6 19:38
加载中...