xtu 1487

二分

#includeusing namespace std;#define maxn 100010
int ch[maxn];
long long sum[maxn];
int n,t,k;bool check(int a){for(int i=1;i<=t;i++){if((sum[i]-i*a)<0){return 0;}}return 1;
}int main(){cin>>n>>t>>k;ch[0]=n;sum[0]=n;for(int i=0;i<k;i++){int d;cin>>d;cin>>ch[d];//第d天提供ch[d]的原材料 }//前缀和 for(int i=1;i<=t;i++){sum[i]=ch[i]+sum[i-1];//1cout<} int tag=1;//是否二分标志// 由于结果必须是整数 因此最小值为1//假设每天消耗1单位原材料 如果有哪天不能满足 则将tag置0 for(int i=1;i<=t;i++){if((sum[i]-i)<0){tag=0;}}//满足则继续二分求最大值 int l=1;//边界 int r=1e9;//边界//闭区间二分【l,r】 if(tag==1){//二分 while(l<=r){int m=(l+r)>>1;if(check(m)){l=m+1;}else{r=m-1;}}}if(tag){cout<<l-1<<endl;}else{cout<<"0"<<endl;}
} ```

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！