我的代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rp(i,j,k) for(int i=j;i<=k;i++)
#define pr(i,k,j) for(int i=k;i>=j;i--)
#define f(i,j,k,p) for(int i=j;i<=k;i+=p)
int n,h,tot,pre[300001],s[3000001];
struct sk{
	int t,d;
}v[300001],eff[300001];
bool cmp(sk a,sk b){return a.t<b.t;}
map<int,int>m;
int check(int t){
	int ls=0,H=h;
	
	rp(i,1,tot){
		int l=ls+1,r=min(t,eff[i].t);
		if(l>r)return 0;
		int ca=pre[i-1],cb=s[i];
		int dft=ca/cb+1;
		
		if(dft<=l){
			int a=cb*l,b=cb*r;
			if(r-l+1>=H*2/(a+b)+((H*2)%(a+b)!=0))return 1;
			H-=(r-l+1)*(a+b)/2;
		}
		else if (dft>r){
			if(ca>=H/(r-l+1)+(H%(r-l+1)!=0))return 1;
			H-=(r-l+1)*ca;
		}
		else{
			int pd=dft-1;
			if(ca>=H/pd+(H%pd!=0))return 1;
			H-=ca*pd;
			int a=cb*dft,b=cb*r;
			if((a+b)>=H*2/(r-dft+1)+((H*2)%(r-dft+1)!=0)){
				return 1;
			}
			H-=(a+b)*(r-dft+1)/2;
		}
		ls=eff[i].t;
		
	}
	int rst=t-ls;
	if(rst>=H/pre[tot]+(H%pre[tot]!=0))return 1;
	return 0;
}
int find(int l,int r){
	int ans=0;
	while(l<=r){
		int mid=l+(r-l)/2;
	//	cout<<mid<<' '<<check(mid)<<endl;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<endl;
}
signed main(){
	cin>>n>>h;
	rp(i,1,n)cin>>v[i].t>>v[i].d;
	rp(i,1,n){
		if(m[v[i].t])eff[m[v[i].t]].d=max(eff[m[v[i].t]].d,v[i].d); else eff[++tot]=v[i],m[v[i].t]=tot;
	}
	sort(eff+1,eff+tot+1,cmp);
	rp(i,1,tot)pre[i]=max(pre[i-1],eff[i].t*eff[i].d);
	for(int i=tot;i>=1;i--)s[i]=max(s[i+1],eff[i].d);
	find(1,h);
	
}

题解代码

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3e5+10; 
int n,h,tot,pre[MAXN],suf[MAXN]; struct Skill {int t,d;}v[MAXN],eff[MAXN];
map<int,int> mp;
int check(int t) {
	int lst=0,H=h;
	ffor(i,1,tot) {
		int l=lst+1,r=min(t,eff[i].t); //在 i 之前的都是原值,在 i 后的都是乘上 i
		if(l>r) return 0;
		int csa=pre[i-1],csb=suf[i];
		int dft=csa/csb+1;
		if(dft<=l) {
			int A=csb*l,B=csb*r;
			if(r-l+1>=H*2/(A+B)+((H*2)%(A+B)!=0)) return 1;
			H-=(r-l+1)*(A+B)/2;
		}
		else if(dft>r) {
			if(csa>=H/(r-l+1)+(H%(r-l+1)!=0)) return 1;
			H-=(r-l+1)*csa;	
		}
		else {
			int prda=dft-l;
			if(csa>=H/prda+(H%prda!=0)) return 1;
			H-=csa*prda;
			int A=csb*dft,B=csb*r;
			if((A+B)>=H*2/(r-dft+1)+((H*2)%(r-dft+1)!=0)) return 1;
			H-=(A+B)*(r-dft+1)/2;
		}
		lst=eff[i].t;
	}
	int rst=t-lst;
	if(rst>=H/pre[tot]+(H%pre[tot]!=0)) return 1;
	return 0;
}
int bfind(int l,int r) {
	int ans=0;
	while(l<=r) {
		int mid=l+(r-l)/2;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>h;
	ffor(i,1,n) cin>>v[i].t>>v[i].d;
	ffor(i,1,n) if(mp[v[i].t]) eff[mp[v[i].t]].d=max(eff[mp[v[i].t]].d,v[i].d); else eff[++tot]=v[i],mp[v[i].t]=tot;
	sort(eff+1,eff+tot+1,[](Skill A,Skill B){return A.t<B.t;});
	ffor(i,1,tot) pre[i]=max(pre[i-1],eff[i].t*eff[i].d);
	roff(i,tot,1) suf[i]=max(suf[i+1],eff[i].d);
	cout<<bfind(1,h); 
	return 0;
}

我看了6遍了，明明代码几乎一致，问题呢？

（玄关）