二分——Schedule Management

点击进入题目

思路描述

用二分，二分时间，看这段时间内工人们的工作量。在这段时间内，每个工人都先做自己擅长做的，然后再干自己不擅长干的，计算出总工作量。

#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int n,m; int a[N]; map<int,int>q; bool check(int mid) { int sum=0; for(int i=1;i<=n;i++) { if(q[i]>=mid) sum+=mid; else sum+=(q[i]+(mid-q[i])/2); } if(sum>=m) return true; return false; } void solve() { q.clear(); cin>>n>>m; for(int i=1;i<=m;i++) cin>>a[i],q[a[i]]++; int l=1; int r=2*m; while(l<r) { int mid=(l+r)/2; if(check(mid)) r=mid; else l=l+1; } cout<<l<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T;cin>>T; while(T--) { solve(); } return 0; }

这一道题乍一看还真不会做，就是连思路也没有。主要是没往二分上去想，后来知道用二分，写的也蛮快的。

新的一天，共勉！