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

小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. 2 4
3. 3 2
4. 4 2
5. 2 2
6. 2 10
7. 3 15

复制代码

样例输出 1

1. 5
2. -1

复制代码

样例输入 2

1. 2
2. 1 5
3. 4
4. 2
5. 1 6
6. 4
7. 2

复制代码

样例输出 2

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

这道题貌似要加快读，否则会被卡常。快读讲解文章

1. #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. 2
3. ，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
4. 2
5. , 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;}

复制代码

附：上面提到的被卡超时的代码

1. //超时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. 2
3. , 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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
2
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。