RT

如果说这题的数据点 #1正如@chen_zhe在帖子这题样例对吗中所说的， 输入是

10 9 18 150 100

输出是

66

注：事实上，由如下两次WA的信息可知，输出确实是 $66$ ——左图告诉我们第一位是 $6$ ，右图告诉我们第二位也是 $6$ 。

这题是构造不出结果 $\geq 660$ 的数据的。因为即使 $t_1,t_2,t_3$ 都取最大值 $18$ ，那么直接让开始的 $4$ 个SCV先挖矿再挖气，挖满 $150+150$ 的时间也只需要 $⌈⌈150 \div 8⌉ \div 4⌉ \times 18 \times 2=180<660$ 。

但是，考虑以下构造：

不造SCV，开局的4个SCV中2个全程挖矿，在 $64$ 秒内可以挖 $⌊64 \div 10⌋ \times 8 \times 2=6 \times 8 \times 2=96$ 矿

第3个SCV先挖一次矿，用时 $10$ 秒，挖了 $8$ 矿。然后再采 $54$ 秒的气，可以采集 $6 \times 8=48$ 的气体

第4个SCV全程采气，可以采集 $⌊64 \div 9⌋ \times 8=7 \times 8=56$ 气

综上，在 $64$ 秒内挖了 $96+8=104$ 矿，加上一开始的 $50$ 矿，一共有 $105+50=154>150$ ；采集了 $48+56=104>100$ 的气体。

于是我们给出了一个 $64$ 的构造。所以本题的第一组数据疑似有误

此外，你谷的评测机似乎炸了：

在某次提交中，我写了一个假定至多建造1个SCV的问题的程序，代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int t1,t2,t3,p1,p2;
int nbu=0;
int rmin=1e9;
class dfs_l{
public:
	bool flag;
	int* a;
	int* s;
	int tot;
	int t;
	int n_gas;
	int ofs;
	int n_ore;
	dfs_l(){}
	~dfs_l(){}
	int calc_birth(int x){//计算x的建造完成时间
		//满足两个条件:s[x]>=s[x-1]+t3且sum_of_ore(s[x]-t3)>=50
		//先算sum_of_ore
		int tore=1e9,sore=0;
		int l=s[x-1],r=rmin,mid;
		while(l<=r){
			mid=(l+r)>>1;
			sore=0;
			for(int i=1;i<=x-1;i++){
				sore+=max(0,min(((mid-s[i])/t1)*8,a[i]*8));//可能还没工作完 or 达成矿的KPI了
			}
			if(sore>=50){
				tore=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		if(tore>=rmin){
			return -1;
		}else{
			return s[x]=tore+t3;
		}
	}
	void dfs_linear(int x){
		if(flag)return;
		if(x==tot){
			int sm=0;
			for(int i=1;i<=x-1;i++){
				sm+=a[i];
			}
			a[x]=n_ore+ofs-sm;
			if(a[x]*t1>=t||calc_birth(x)==-1){
				return;
			}
			int sum=0;
			for(int i=1;i<=tot;i++){
				sum+=(t-s[i]-a[i]*t1)/t2;
			}
			if(sum>=n_gas){
//				cout<<"["<<t<<","<<x<<"]:";
//				for(int i=1;i<=tot;i++){
//					cout<<a[i]<<" ";
//				}
//				cout<<endl;
				flag=1;
			}
			return;
		}
		int sm=0;
		for(int i=1;i<=x-1;i++){
			sm+=a[i];
		}
		if(x<=4){
			for(a[x]=a[x-1];sm+a[x]*(4-x+1)<=n_ore+ofs&&a[x]*t1<=t;a[x]++){
				dfs_linear(x+1);
			}
		}else if(x==5){
			for(a[x]=0;sm+a[x]<=n_ore+ofs&&a[x]*t1+t3<=t;a[x]++){
				dfs_linear(x+1);
			}
		}else{
			if(calc_birth(x)==-1){
				return;
			}
			for(a[x]=0;a[x]+sm<=n_ore+ofs&&a[x]*t1+s[x]<=t;a[x]++){
				dfs_linear(x+1);
			}
		}
	}
};
void validate_min_of_noscv(){//计算不造SCV时的tmin
	int res=1e9;//结果
	//一共4个SCV要挖(p1-50+7)/8次矿和(p2+7)/8次气
	int n_ore=max((p1-50+7)/8,0),n_gas=(p2+7)/8;
	//假设第i个SCV挖ai次矿和bi次气
	//那么:ai*t1+bi*t2<=res
	//且:Σ(ai)>=n_ore,Σ(bi)>=n_gas
	//我的天哪,是线性规划,我们死定了
	//n_ore<=13;n_gas<=19
	int a[6]={0};
	int l=0,r=rmin,mid;
	while(l<=r){
		mid=(l+r)>>1;
//		cout<<mid<<endl;
		bool flag=0;
		for(a[1]=0;a[1]*4<=n_ore&&a[1]*t1<=mid;a[1]++){
			for(a[2]=a[1];a[1]+a[2]*3<=n_ore&&a[2]*t1<=mid;a[2]++){
				for(a[3]=a[2];a[1]+a[2]+a[3]*2<=n_ore&&a[3]*t1<=mid;a[3]++){
					a[4]=n_ore-a[1]-a[2]-a[3];
//					cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<endl;
//					cout<<a[1]+a[2]+(a[3]+1)*2<<"<="<<n_ore<<"||"<<(a[3]+1)*t1<<"<="<<mid<<endl;
					if(a[4]*t1>mid)continue;
					int sum=0;
					for(int i=1;i<=4;i++){
						sum+=(mid-a[i]*t1)/t2;
					}
					if(sum>=n_gas){
						flag=1;
						break;
					}
				}
				if(flag)break;
			}
			if(flag)break;
		}
		if(flag){
//			cout<<mid<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<endl;
			res=mid,r=mid-1;
		}else{
			l=mid+1;
		}
	}
	rmin=min(rmin,res);
}
void validate_min_of_1scv(){//计算造1个SCV时的tmin
	int res=1e9;//结果
	//一共4+1个SCV要挖(p1+7)/8次矿和(p2+7)/8次气
	int n_ore=(p1+7)/8,n_gas=(p2+7)/8;
	//假设第i个SCV挖ai次矿和bi次气
	//那么:ai*t1+bi*t2<=res(i<=4)
	//且a5*t1+b5*t2<=res-t3
	//且:Σ(ai)>=n_ore,Σ(bi)>=n_gas
	int a[6]={0};
	int l=0,r=rmin,mid;
	while(l<=r){
		mid=(l+r)>>1;
		bool flag=0;
		for(a[1]=0;a[1]*4<=n_ore&&a[1]*t1<=mid;a[1]++){
			for(a[2]=a[1];a[1]+a[2]*3<=n_ore&&a[2]*t1<=mid;a[2]++){
				for(a[3]=a[2];a[1]+a[2]+a[3]*2<=n_ore&&a[3]*t1<=mid;a[3]++){
					for(a[4]=a[3];a[1]+a[2]+a[3]+a[4]<=n_ore&&a[4]*t1<=mid;a[4]++){
						a[5]=n_ore-a[1]-a[2]-a[3]-a[4];
						if(a[5]*t1+t3>mid)continue;
						int sum=0;
						for(int i=1;i<=4;i++){
							sum+=(mid-a[i]*t1)/t2;
						}
						sum+=(mid-t3-a[5]*t1)/t2;
						if(sum>=n_gas){
							flag=1;
							break;
						}
					}
				}
				if(flag)break;
			}
			if(flag)break;
		}
		if(flag){
			res=mid,r=mid-1;
		}else{
			l=mid+1;
		}
	}
	rmin=min(rmin,res);
}
void validate_min_of_kscv(int k){//k>=1
	//不难证明:先挖一定量的矿把SCV造好了比什么都强
	//具体证明留给读者
	int res=1e9;
	int n_gas=(p2+7)/8;
	int ore_for_scv=max(((k-1)*50+7)/8,0);
	int n_ore=(p1+(k-1)*50-ore_for_scv*8+7)/8;
	int a[114]={0},s[114]={0};//s:启动!时间
	int l=1,r=rmin;
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		for(int i=5;i<=k+4;i++){
			s[i]=-1;
		}
		s[5]=t3;
		dfs_l mdl;
		mdl.a=a;
		mdl.s=s;
		mdl.tot=k+4;
		mdl.t=mid;
		mdl.n_gas=n_gas;
		mdl.n_ore=n_ore;
		mdl.ofs=ore_for_scv;
		mdl.flag=0;
		mdl.dfs_linear(1);//验证mid是否可行,存在flag里
		if(mdl.flag){
			res=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	rmin=min(rmin,res);
}
int main(){
    cin>>t1>>t2>>t3>>p1>>p2;
    //枚举补几个
    if(p1<=50)
    	rmin=(((p2+3)/4+7)/8)*t2;
    else
    	rmin=((((p1-50+3)/4+7)/8)*t1+(((p2+3)/4+7)/8)*t2);
    validate_min_of_noscv();
    validate_min_of_1scv();
    for(nbu=2;nbu<=4;nbu++){
		// validate_min_of_kscv(nbu);
    }
    cout<<rmin<<endl;
}

这是评测记录R218184823，可以看到第一个点是AC的。但是，在在线IDE中运行它，输出的结果却是64。

此外，@pulsar_在R199049289中的代码移植到本地，用 -std=gnu++14 -O2 编译运行之后可以发现输出的结果也是 $64$ 。（我试了一下，不能在在线IDE中运行，因为我发现一旦运行时间超过1秒之后就会显示TLE）

大概是洛谷日爆吧

最后以下是我的代码，求调（我也不知道为什么我一个退役快两年的信竞蒟蒻会突然心血来潮来做这道题，大概是因为我必须重新集结部队吧）

主要是有一个诡异的#28过不了（可能是需要补的SCV太多以至于来不及搜索到它的解）

这是评测记录R218185165

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int t1,t2,t3,p1,p2;
int nbu=0;
int rmin=1e9,tg;
class dfs_l{
public:
	bool flag;
	int* a;
	int* s;
	int tot;
	int t;
	int n_gas;
	int ofs;
	int n_ore;
	dfs_l(){}
	~dfs_l(){}
	int calc_birth(int x){//计算x的建造完成时间
		//满足两个条件:s[x]>=s[x-1]+t3且sum_of_ore(s[x]-t3)>=50
		//先算sum_of_ore
		int tore=1e9,sore=0;
		int l=s[x-1],r=rmin,mid;
		while(l<=r){
			mid=(l+r)>>1;
			sore=0;
			for(int i=1;i<=x-1;i++){
				sore+=max(0,min(((mid-s[i])/t1)*8,a[i]*8));//可能还没工作完 or 已经达成矿的KPI了
			}
			if(sore>=50){
				tore=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		if(tore>=rmin){
			return -1;
		}else{
			return s[x]=tore+t3;
		}
	}
	void dfs_linear(int x){
		if(flag)return;
		if(clock()-tg>=9.9f*(double)CLOCKS_PER_SEC)return;
		if(x==tot){
			int sm=0;
			for(int i=1;i<=x-1;i++){
				sm+=a[i];
			}
			a[x]=n_ore+ofs-sm;
			if(a[x]*t1>=t||calc_birth(x)==-1){
				return;
			}
			int sum=0;
			for(int i=1;i<=tot;i++){
				sum+=(t-s[i]-a[i]*t1)/t2;
			}
			if(sum>=n_gas){
				flag=1;
			}
			return;
		}
		int sm=0;
		for(int i=1;i<=x-1;i++){
			sm+=a[i];
		}
		if(x<=4){
			for(a[x]=a[x-1];sm+a[x]*(4-x+1)<=n_ore+ofs&&a[x]*t1<=t;a[x]++){
				dfs_linear(x+1);
			}
		}else if(x==5){
			for(a[x]=0;sm+a[x]<=n_ore+ofs&&a[x]*t1+t3<=t;a[x]++){
				dfs_linear(x+1);
			}
		}else{
			if(calc_birth(x)==-1){
				return;
			}
			for(a[x]=0;a[x]+sm<=n_ore+ofs&&a[x]*t1+s[x]<=t;a[x]++){
				dfs_linear(x+1);
			}
		}
	}
};
int validate_min_of_noscv(){//计算不造SCV时的tmin
	int res=1e9;//结果
	//一共4个SCV要挖(p1-50+7)/8次矿和(p2+7)/8次气
	int n_ore=max((p1-50+7)/8,0),n_gas=(p2+7)/8;
	//假设第i个SCV挖ai次矿和bi次气
	//那么:ai*t1+bi*t2<=res
	//且:Σ(ai)>=n_ore,Σ(bi)>=n_gas
	//我的天哪,是线性规划,我们死定了（划掉
	//n_ore<=13;n_gas<=19
	int a[6]={0};
	int l=0,r=rmin,mid;
	while(l<=r){
		mid=(l+r)>>1;
//		cout<<mid<<endl;
		bool flag=0;
		//SCV个数比较少,直接枚举
		for(a[1]=0;a[1]*4<=n_ore&&a[1]*t1<=mid;a[1]++){
			for(a[2]=a[1];a[1]+a[2]*3<=n_ore&&a[2]*t1<=mid;a[2]++){
				for(a[3]=a[2];a[1]+a[2]+a[3]*2<=n_ore&&a[3]*t1<=mid;a[3]++){
					a[4]=n_ore-a[1]-a[2]-a[3];
//					cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<endl;
//					cout<<a[1]+a[2]+(a[3]+1)*2<<"<="<<n_ore<<"||"<<(a[3]+1)*t1<<"<="<<mid<<endl;
					if(a[4]*t1>mid)continue;
					int sum=0;
					for(int i=1;i<=4;i++){
						sum+=(mid-a[i]*t1)/t2;
					}
					if(sum>=n_gas){
						flag=1;
						break;
					}
				}
				if(flag)break;
			}
			if(flag)break;
		}
		if(flag){
//			cout<<mid<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<endl;
			res=mid,r=mid-1;
		}else{
			l=mid+1;
		}
	}
	rmin=min(rmin,res);
	return res;
}
int validate_min_of_1scv(){//计算造1个SCV时的tmin
	int res=1e9;//结果
	//一共4+1个SCV要挖(p1+7)/8次矿和(p2+7)/8次气
	int n_ore=(p1+7)/8,n_gas=(p2+7)/8;
	//假设第i个SCV挖ai次矿和bi次气
	//那么:ai*t1+bi*t2<=res(i<=4)
	//且a5*t1+b5*t2<=res-t3
	//且:Σ(ai)>=n_ore,Σ(bi)>=n_gas
	int a[6]={0};
	int l=0,r=rmin,mid;
	while(l<=r){
		mid=(l+r)>>1;
		bool flag=0;
		//SCV个数还是不算多,继续选择枚举
		for(a[1]=0;a[1]*4<=n_ore&&a[1]*t1<=mid;a[1]++){
			for(a[2]=a[1];a[1]+a[2]*3<=n_ore&&a[2]*t1<=mid;a[2]++){
				for(a[3]=a[2];a[1]+a[2]+a[3]*2<=n_ore&&a[3]*t1<=mid;a[3]++){
					for(a[4]=a[3];a[1]+a[2]+a[3]+a[4]<=n_ore&&a[4]*t1<=mid;a[4]++){
						a[5]=n_ore-a[1]-a[2]-a[3]-a[4];
						if(a[5]*t1+t3>mid)continue;
						int sum=0;
						for(int i=1;i<=4;i++){
							sum+=(mid-a[i]*t1)/t2;
						}
						sum+=(mid-t3-a[5]*t1)/t2;
						if(sum>=n_gas){
							flag=1;
							break;
						}
					}
				}
				if(flag)break;
			}
			if(flag)break;
		}
		if(flag){
			res=mid,r=mid-1;
		}else{
			l=mid+1;
		}
	}
	rmin=min(rmin,res);
	return res;
}
int validate_min_of_kscv(int k){//k>=2
	//猜测:先挖一定量的矿把SCV造好了比什么都强
	int res=1e9;
	int n_gas=(p2+7)/8;
	int ore_for_scv=max(((k-1)*50+7)/8,0);
	int n_ore=(p1+(k-1)*50-ore_for_scv*8+7)/8;
	int a[114]={0},s[114]={0};//s:启动!时间
	int l=1,r=rmin;
	int mid;
	while(l<=r){
		mid=(l+r)>>1;
		for(int i=5;i<=k+4;i++){
			s[i]=-1;
		}
		s[5]=t3;
		a[0]=2;
		dfs_l mdl;
		mdl.a=a;
		mdl.s=s;
		mdl.tot=k+4;
		mdl.t=mid;
		mdl.n_gas=n_gas;
		mdl.n_ore=n_ore;
		mdl.ofs=ore_for_scv;
		mdl.flag=0;
		mdl.dfs_linear(1);//验证mid是否可行,存在flag里
		if(mdl.flag){
			res=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
		if(clock()-tg>=9.9f*(double)CLOCKS_PER_SEC){
			rmin=min(rmin,res);
			return res;
		}
	}
	rmin=min(rmin,res);
	return res;
}
int main(){
	tg=clock();
    cin>>t1>>t2>>t3>>p1>>p2;
    if(p1<=50)
    	rmin=(((p2+3)/4+7)/8)*t2;
    else
    	rmin=((((p1-50+3)/4+7)/8)*t1+(((p2+3)/4+7)/8)*t2);
    int rmins[100]={0};
    rmins[0]=validate_min_of_noscv();
    rmins[1]=validate_min_of_1scv();
    for(nbu=2;;nbu++){
		rmins[nbu]=validate_min_of_kscv(nbu);
		if(rmins[nbu]==rmins[nbu-2])break;//再枚举下去应该就不会变了
		if(clock()-tg>=9.9f*(double)CLOCKS_PER_SEC)break;//防超时
    }
    cout<<rmin<<endl;
}