微信怎么做捐钱的网站,东莞seo网络公司,济南市建设网站,用wordpress设计html文章目录 小S与机房里的电脑 Computer传统题题目描述输入格式输出格式样例样例输入 1样例输出 1样例输入 2样例输出 2 提示解题思路AC CodeEnd 小S与机房里的电脑 Computer
传统题
时间限制: 1000ms内存限制: 256MiB
题目描述
最近小S想带他的学生打组队娱乐赛#xff0c;… 文章目录 小S与机房里的电脑 Computer传统题题目描述输入格式输出格式样例样例输入 1样例输出 1样例输入 2样例输出 2 提示解题思路AC CodeEnd 小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
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 ≤ 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 12 1 \leq a_i \leq 10^{12} 1≤ai≤1012 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[i] ves[i] 表示存活时间到 i i i 的电脑的结构体下标数组
去枚举 vector 的第一维下标同时设置一个变量 n o w T nowT nowT 表示当前时间
根据贪心的思想选择当前快要没电的那个存活时间到 i i i 的先充电
如果当前时间大于第一维下标说明电脑修不过来了返回 false
否则 n o w T m nowT m nowTm 时说明执行完任务了退出。
小总结
check 中的循环调换了常理。原本正常的思路应该是枚举 n o w T nowT nowT用堆维护当前的最小存活时间如 AC 代码下面的代码
但是这样复杂度 O ( log ( 1 0 12 ) × m × log ( n ) ) O(\log(10^{12}) \times m \times \log(n)) O(log(1012)×m×log(n))但“好心”的出题人卡 log说明不能这样。
于是我们转而枚举第一维下标解决了问题这种思路很值得积累。 程序运行过程
输入用结构体存储每一台电脑的基础信息和存活时间。二分答案充电功率往小了二分。
check(){
预处理每一台电脑用 vector 建桶这样查询插入复杂度 O ( 1 ) O(1) O(1)。不断枚举 vector 的第一维下标不断修电脑直到有的电脑最大存活时间小于当前枚举的时间退出。一直执行至 n o w T m nowT m nowTm说明可以完成任务返回 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]1e12m不强转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
