CF. Schedule Management

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
int a[N];
int n , m;
map<int, LL>mp;
bool check(LL x)
{
  LL sum = 0 , tmp = 0;
   for(int i = 1; i <= n; i ++)
   {
     if(mp[i] > x)sum += mp[i] - x;
     else tmp += (x - mp[i]) / 2;
   }
   return tmp >= sum;
}
int main()
{
  int t;
  cin >> t;
  while(t --)
  {
    mp.clear();
    cin >> n >> m;
    
    for(int i = 1; i <= m; i ++)
    {
      cin >> a[i];
      mp[a[i]] ++;
    }
    LL l = 0, r = 1e10;
    while(l < r)
    {
      LL mid = (l + r) >> 1;
      if(check(mid))r = mid;
      else l = mid + 1;
    }
    cout << l << endl;
  }
}

二分时间的条件就是 每个工人在设定的时间内能干的最多任务之和 与 m 比较, 如果大于m则缩短时间,否则增加时间(工人首先干自己精通的任务,其次用剩余的时间干不精通的任务 )

全部评论

相关推荐

07-11 11:10
门头沟学院 Java
请问各位大三兄弟们跟hr说多久实习时间到时候可以提前跑路吗?
程序员小白条:问就是六个月以上,可以一年,实习都这样,你入职后想跑就跑
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-11 12:10
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务