首页 > 其他 > 详细

2019-2020 ACM-ICPC Brazil Subregional Programming Contest Problem M Maratona Brasileira de Popcorn (二分)

时间:2020-06-22 13:57:24      阅读:83      评论:0      收藏:0      [点我收藏+]

技术分享图片

  • 题意:有\(n\)袋爆米花,某个队伍有\(c\)个队员,每个队员每秒做多可以吃\(t\)粒爆米花,但一袋爆米花只能由一个队员吃完,并且一个队员只能吃连续的一袋或几袋,不能隔着吃某一袋,求将所有爆米花吃完的最少时间.

  • 题解:这道题当时想了半天,发现怎么也求不出答案,后来想到了二分答案的办法,将答案代入并模拟题意判断看是否满足条件,二分求得最小值即可.

  • 代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <bitset>
    #include <unordered_set>
    #include <unordered_map>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
     
    int n,c,t;
    ll a[N];
     
    bool check(ll x){
    	ll num=1;
    	ll sum=0;
    	ll now=x*t;
    	for(int i=1;i<=n;++i){
    		if(a[i]>now){
    			return false;
    		}
    		if(sum+a[i]>now){
    			num++;
    			sum=a[i];
    		}
    		else{
    			sum+=a[i];
    		}
    	}
    	if(num<=c) return true;
    	else return false;
    }
     
    int main() {
        ios::sync_with_stdio(false);cin.tie(0);
    	cin>>n>>c>>t;
    	for(int i=1;i<=n;++i){
    		cin>>a[i];
    	}
    	ll l=1,r=INF;
    	while(l<r){                 //模板:向左二分
    		ll mid=l+r>>1;
    		if(check(mid)) r=mid;
    		else l=mid+1;
    	}
    	cout<<r<<endl;
    	
        return 0;
    }
    

2019-2020 ACM-ICPC Brazil Subregional Programming Contest Problem M Maratona Brasileira de Popcorn (二分)

原文:https://www.cnblogs.com/lr599909928/p/13176406.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!