C. Schedule Management

链接: problem

分析：

这句话应该会让你立刻联想到二分。很明显，如果你能以在

t

t

t 时间之前完成任务的方式分配工人，那么你也能在

t

+

1

t+1

t+1 或更长时间之前完成所有任务。

如何检查任务是否能在某个时间

t

t

t 前完成呢？这意味着所有工人都有

t

t

t 个小时来完成某些任务。如果所有任务都需要

2

2

2 小时才能完成，那么他们每个人都可以完成

?

t

2

?

lfloor frac t 2
floor

?2t?? 项任务。因此，他们总共可以完成

?

t

2

?

?

n

lfloor frac t 2
floor cdot n

?2t???n 项任务。

如何将

1

1

1 小时的任务纳入其中呢？我们可以重新分配任务，让每个工人先完成自己擅长的任务，如果时间充裕，再完成其他任务。

总体思路如下。让每个工人

i

i

i 完成

m

i

n

(

t

,

c

n

t

i

)

min(t, mathit{cnt}_i)

min(t,cnti?) 小时的任务。

1

1

1 小时的任务，其中

c

n

t

i

mathit{cnt}_i

cnti? 是

i

i

i 个工人所精通的任务数。然后记住他们能完成多少

2

2

2 /小时的任务，即

?

t

?

m

i

n

(

t

,

c

n

t

i

)

2

?

lfloor frac{t - min(t, mathit{cnt}_i)}{2}
floor

?2t?min(t,cnti?)?? 。最后，记住他们精通的任务中有多少没有时间完成，即

c

n

t

i

?

m

i

n

(

t

,

c

n

t

i

)

mathit{cnt}_i - min(t, mathit{cnt}_i)

cnti??min(t,cnti?) 。如果未完成任务数的总和不超过他们有时间完成的任务数的总和，那么所有任务都可以在

t

t

t 时间内完成。

最糟糕的情况是，如果将所有任务分配给一名工人，而他又不精通其中任何一项，那么完成所有任务可能需要

2

m

2m

2m 个小时。

总体复杂度：每个测试案例

O

(

n

log

?

m

)

O(n log m)

O(nlogm) 。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=1e9+10;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int cnt[N];
int n,m;
bool check(int t)
{
    ll t1=0,t2=0;
    for(int i=1;i<=n;i++)
    {
      if(t>=cnt[i]) t1+=(t-cnt[i])/2;
      else t2+=(cnt[i]-t);
    }
    if(t1>=t2) return true;
    else return false; 
}
void solve()
{
   cin>>n>>m;
   for(int i=1;i<=n;i++) cnt[i]=0;
   for(int i=1,x;i<=m;i++) cin>>x,cnt[x]++;
   int l=0,r=m+1;
   while(l+1!=r)
   {
    int mid=(l+r)/2;
    if(check(mid)) r=mid;
    else l=mid;
   } 
   cout<<r<<endl;
   return ;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) 
    solve();
    return 0;
}