云服务器 部署网站,品牌营销是什么,哪些知名网站用wordpress,培训机构学校思路#xff1a;利用二分找到某个时间是满足“k个人可以完成” #xff0c;并且时间最小。
因为尽量让后面的人做任务#xff0c;所以从后往前排任务#xff08;倒着分配#xff09;。从后往前遍历任务#xff0c;如果此人加上这个任务超出之前求得的时间#xff0c;就…
思路利用二分找到某个时间是满足“k个人可以完成” 并且时间最小。
因为尽量让后面的人做任务所以从后往前排任务倒着分配。从后往前遍历任务如果此人加上这个任务超出之前求得的时间就移到上一个人。 #include bits/stdc.h
using namespace std;
#define int long long
const int N 1e4 10;
int t, k;
int ti[N];bool check(int u)
{ // u秒可不可以由k个人完成int s 1; // 记录当前的人int a[N]; // 记录每人任务时间memset(a, 0, sizeof(a));for (int i 1; i t; i) // 遍历t个任务{if (a[s] ti[i] u) // 如果当前时间加上当前任务的时间大于u{s; // 选下一个人a[s] ti[i];}elsea[s] ti[i];}if (s k){ // 人数kreturn false;}return true;
}
int c[N][2]; //[每人][起点终点]
void print(int u)
{ // u为时间// 倒着分配int i k, temp 0;for (int j t; j 0; j--){if (c[i][1] 0){ // 结束c[i][1] j;}if (temp ti[j] u) // 时间超出则换人从后往前i--{c[i][0] j 1;i--;temp ti[j];c[i][1] j; // 结束}else{ // 时间未超出temp ti[j];}}c[i][0] 1;for (int i 1; i k; i){if (c[i][0] 0)cout 0 0 endl;elsecout c[i][0] c[i][1] endl;}
}
signed main()
{int l -1, r 0, ans 0;cin t k;for (int i 1; i t; i){cin ti[i];l max(l, ti[i]);//记录最大时间r ti[i];//记录总时间}// 二分任务的时间while (l r){int mid (l r) / 2;if (check(mid)){r mid - 1;ans mid;}else{l mid 1;}}print(ans);return 0;
}
