小S与机房里的电脑 Computer
传统题
- 时间限定: 1000ms
- 内存限定: 256MiB
题目形貌
最近小S想带他的学生打组队娱乐赛，角逐规定每队三个人只能其中一个人用电脑进行代码的编写。
但是现在隔壁课堂因为上大型集训课拿走了所有的充电器，导致最后只剩下一个充电器可以拿来充电。但是 n n n 个队伍必要 n n n 台电脑，而且组队娱乐赛要进行 m m m 分钟，每台电脑有初始的电量 a i a_i ai ，每分钟的耗电量 b i b_i bi 。没有办法，小S只能通过他的电路知识来改装这个充电器，使得它具有充足的功率来帮助同砚们完成这场角逐。
但是功率越大危险度越高，小S希望你帮他盘算一下，充电器至少每分钟要充多少电才能满意大家的需求。
输入格式
- 第一行一个正整数 T T T 代表多组数据的组数
- 第二行两个整数 n n n 和 m m m
- 第三行 n n n 个整数 a i a_i ai
- 第四行 n n n 个整数 b i b_i bi
输出格式
输出一行整数，代表满意角逐需求的充电器每分钟最小的充电量，若无法满意需求，则输出 -1。
样例
样例输入 1
样例输出 1
样例输入 2
样例输出 2
提示
全部数据包括：
- n ≤ 2 × 1 0 5 n \leq 2 \times 10^5 n≤2×105
- 1 ≤ m ≤ 2 × 1 0 5 1 \leq m \leq 2 \times 10^5 1≤m≤2×105
- 1 ≤ a i ≤ 1 0 1
2
1 \leq a_i \leq 10^{1
2
} 1≤ai≤101
2
- 1 ≤ b i ≤ 1 0 7 1 \leq b_i \leq 10^7 1≤bi≤107
其中，30%的数据保证 n ≤ 100 n \leq 100 n≤100
解题思路
提示：这里光看有些抽象，连合下面的 Code 明白起来更容易。
思路：思量二分答案，二分最小的充电功率。
其中可以用 vector 建桶， v e s [ i ] ves ves 表示存活时间到 i i i 的电脑的布局体下标数组，
去枚举 vector 的第一维下标，同时设置一个变量 n o w T nowT nowT 表示当前时间，
根据贪婪的思想，选择当前将近没电的那个：存活时间到 i i i 的先充电
如果当前时间大于第一维下标，说明电脑修不过来了，返回 false；
否则， n o w T = m nowT =m nowT=m 时，说明执行完使命了，退出。
小总结：
check 中的循环变更了常理。原本正常的思路应该是枚举 n o w T nowT nowT，用堆维护当前的最小存活时间（如 AC 代码下面的代码），
但是这样复杂度 O ( log ( 1 0 1
2
) × m × log ( n ) ) O(\log(10^{1
2
}) \times m \times \log(n)) O(log(101
2
)×m×log(n))，但“美意”的出题人卡 log，说明不能这样。
于是，我们转而枚举第一维下标办理了题目，这种思路很值得积累。
程序运行过程：
- 输入，用布局体存储每一台电脑的底子信息和存活时间。
- 二分答案，充电功率，往小了二分。
check(){
- 预处置惩罚每一台电脑，用 vector 建桶，这样查询插入复杂度 O ( 1 ) O(1) O(1)。
- 不停枚举 vector 的第一维下标，不停修电脑，直到有的电脑最大存活时间小于当前枚举的时间，退出。
- 一直执行至 n o w T = m nowT = m nowT=m，说明可以完成使命，返回 TRUE。
}
AC Code
这道题貌似要加快读，否则会被卡常。快读讲解文章
- #include <bits/stdc++.h>using namespace std;typedef long long ll;int T, n, m;struct Node{ ll a, b; ll t_a; // 表示当前还能存活多长时间}N[100005];vector <int> A[100005];bool check(ll x){ for(int i = 0; i <= m; i ++) A[i].clear(); // 先清空，后使用 for(int i = 1; i <= n; i ++){ // 初始化赋值 N[i].t_a = N[i].a; if(N[i].b != 0 && N[i].t_a / N[i].b + 1 <= m){ // 如果存活时间在m之内，说明还有盘算的必要（它大概会撑不住） A[N[i].t_a / N[i].b + 1].push_back(i); // 塞到对应的桶中 } } int nowT = 1; // 当前时间的计数器 for(int i = 1; i <= m; i ++){ // 枚举m个时间单元，作为判断标准（可以明白为理想化的时间） while(A[i].size() > 0){ // 这个内层循环最多执行n次，以是总时间复杂度不是O(n^2)，是线性O(n)的 if(nowT > i){ // 如果当前时间>i，说明已经超时了 return false; } if(nowT == m){ return true; // 说明顺利执行完m秒，可以返回 } int pos = A[i].back(); A[i].pop_back(); N[pos].t_a += x; // 把充电器给他充上。因为当前的压线时间是i，以是肯定要先给快没电的（也就是当前时间i）充电。至于先后顺序就无所谓了。 nowT ++; if(N[pos].t_a / N[pos].b + 1 <= 1LL * m){ // 注意a[i]<=1e1
- 2
- ，m不强转ll大概会出题目 A[N[pos].t_a / N[pos].b + 1].push_back(pos); }// cout << "debug: " << i << " " << A[i].size() << " " << nowT << endl; }// cout << "debug_i:" << i << endl; } return true;}template <typename T>void read(T &w){ // 防止卡常，加快读 w = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()); for(; c >= '0' && c <= '9'; c = getchar()){ w = (w << 1) + (w << 3) + (c ^ 48); }}int main(){ for(read(T); T --; ){ read(n), read(m); for(int i = 1; i <= n; i ++){ read(N[i].a); } for(int i = 1; i <= n; i ++){ read(N[i].b); }// cout << check(10) << endl; ll l = 0, r = 1e1
- 2
- , ans = -1; while(l <= r){ ll mid = (l + r) >> 1; if(check(mid)){ ans = mid; r = mid - 1; }else{ l = mid + 1; } } printf("%lld\n", ans); } return 0;}
- //超时TLE#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 2e5 + 7;int T , n , m;struct Node{ ll a , b; ll t_a;}no[MAXN];bool check(ll x){ map < int , vector <int> > vis; for(int i = 1; i <= n; i ++){ //预处置惩罚 no[i].t_a = no[i].a; if(no[i].b != 0 && no[i].t_a / no[i].b < 1LL * m){ vis[no[i].t_a / no[i].b].push_back(i); }else{ //pass } } for(int tim = 0; tim < m; tim ++){ if(vis.empty()){ return true; } int pos = vis.begin()->first; if(pos < tim){ return false; } ll t1 = vis[pos].back(); vis[pos].pop_back(); if(vis[pos].size() == 0){ vis.erase(vis.begin()); } no[t1].t_a += x; if(no[t1].t_a / no[t1].b < m){ vis[no[t1].t_a / no[t1].b].push_back(t1); } } return true;}int main(){ for(scanf("%d" , &T); T; --T){ scanf("%d %d" , &n , &m); for(int i = 1; i <= n; i ++){ scanf("%lld" , &no[i].a); } for(int i = 1; i <= n; i ++){ scanf("%lld" , &no[i].b); }// cout << check(5) << endl; ll l = 0 , r = 1e1
- 2
- , ans = -1; while(l <= r){ //二分充电功率，往小了二分 ll mid = (l + r) >> 1; if(check(mid)){ ans = mid; r = mid - 1; }else{ l = mid + 1; } } printf("%lld\n" , ans); } return 0;}
感谢大家观看，祝大家 AC！
这里是 YLCHUP，拜拜ヾ(•ω•`)o
广告：本文在洛谷博客同步发送，个人洛谷账号：ylch
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
2
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
