题解：小S与机房里的电脑 Computer_C++算法竞赛_贪心_二分答案_模拟_数据结构

文章目录

• 小S与机房里的电脑 Computer
• • 传统题
  • 题目描述
  • 输入格式
  • 输出格式
  • 样例
  • • 样例输入 1
    • 样例输出 1
    • 样例输入 2
    • 样例输出 2
  • 提示
  • 解题思路
  • AC Code
  • End

小S与机房里的电脑 Computer

传统题

• 时间限制: 1000ms
• 内存限制: 256MiB

题目描述

最近小S想带他的学生打组队娱乐赛，比赛规定每队三个人只能其中一个人用电脑进行代码的编写。

但是现在隔壁教室因为上大型集训课拿走了所有的充电器，导致最后只剩下一个充电器可以拿来充电。但是 $n$ 个队伍需要 $n$ 台电脑，并且组队娱乐赛要进行 $m$ 分钟，每台电脑有初始的电量 $a_i$ ，每分钟的耗电量 $b_i$ 。没有办法，小S只能通过他的电路知识来改装这个充电器，使得它具有足够的功率来帮助同学们完成这场比赛。

但是功率越大危险度越高，小S希望你帮他计算一下，充电器至少每分钟要充多少电才能满足大家的需求。

输入格式

• 第一行一个正整数 $T$ 代表多组数据的组数
• 第二行两个整数 $n$ 和 $m$
• 第三行 $n$ 个整数 $a_i$
• 第四行 $n$ 个整数 $b_i$

输出格式

输出一行整数，代表满足比赛需求的充电器每分钟最小的充电量，若无法满足需求，则输出 -1。

样例

样例输入 1

2 2 4 3 2 4 2 2 2 2 10 3 15 

样例输出 1

5 -1 

样例输入 2

2 1 5 4 2 1 6 4 2 

样例输出 2

1 2 

提示

全部数据包括：

• $n\le 2\times 10^5$
• $1\le m\le 2\times 10^5$
• $1\le a_i\le 10^{12}$
• $1\le b_i\le 10^7$

其中，30%的数据保证 $n\le 100$

---

解题思路

提示：这里光看有些抽象，结合下面的 Code 理解起来更容易。

思路：考虑二分答案，二分最小的充电功率。

其中可以用 vector 建桶，$ves[i]$ 表示存活时间到 $i$ 的电脑的结构体下标数组，

去枚举 vector 的第一维下标，同时设置一个变量 $nowT$ 表示当前时间，

根据贪心的思想，选择当前快要没电的那个：存活时间到 $i$ 的先充电

如果当前时间大于第一维下标，说明电脑修不过来了，返回 false；

否则，$nowT=m$ 时，说明执行完任务了，退出。

小总结：

check 中的循环调换了常理。原本正常的思路应该是枚举 $nowT$，用堆维护当前的最小存活时间（如 AC 代码下面的代码），

但是这样复杂度 $O(\log (10^{12})\times m\times \log (n))$，但“好心”的出题人卡 log，说明不能这样。

于是，我们转而枚举第一维下标解决了问题，这种思路很值得积累。

---

程序运行过程：

1. 输入，用结构体存储每一台电脑的基础信息和存活时间。
2. 二分答案，充电功率，往小了二分。

check(){

1. 预处理每一台电脑，用 vector 建桶，这样查询插入复杂度 $O(1)$。
2. 不断枚举 vector 的第一维下标，不断修电脑，直到有的电脑最大存活时间小于当前枚举的时间，退出。
3. 一直执行至 $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]<=1e12，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 = 1e12, 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 = 1e12 , 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; } 

End

感谢大家观看，祝大家 AC！

这里是 YLCHUP，拜拜ヾ(•ω•`)o

广告：本文在洛谷博客同步发送，个人洛谷账号：ylch