题意:有\(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;
}
原文:https://www.cnblogs.com/lr599909928/p/13176406.html