又放学辣（进阶）(两次二分或两次后缀和)（小白80D）

D-又放学辣（进阶）_牛客小白月赛80 (nowcoder )

求最大值的最小值，=》二分；

对于check函数，我们要统计cnt=（a[i]-t)的和(t为二分的量),如果cnt<k，说明答案小于t，否则大于t；

时间复杂度为：n*log(n)*log(n)

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<math.h> #include<unordered_map> #include<map> using namespace std; typedef long long LL; #define  per(i,a,b)  for(int i=a;i<=b;i++)  const int  N = 1e6 + 100; int n, k, m, sum, mi; int  a[N], x, b[N]; int  c[N]; bool cmp(int x, int y) {     return x > y; } int check(int x, int i) {        int l = 1, r = m, mid, ans = 0, cha;     while (l <= r)     {         mid = (l + r) / 2;         if (b[mid] >= x)             ans = mid, l = mid + 1;         else             r = mid - 1;     }     if (b[ans] <= a[i])         cha = c[ans] - a[i] - (ans - 1) * x;     else         cha = c[ans] - ans * x;     if (cha <= k||ans==0) return 1;     return 0; } int main() {     scanf("%d%d%d", &n, &m, &k);     per(i, 1, n)     {         scanf("%d", &x);         a[x]++;     }     per(i, 1, m) b[i] = a[i];     sort(b + 1, b + 1 + m, cmp);     per(i, 1, m) c[i] = c[i - 1] + b[i];     int l, r, mid;     per(i, 1, m)     {         if (n < k + a[i])         {             printf("-1 ");             continue;         }         l = 0;         r = n - k - a[i];         mi = -1;         while (l <= r)         {             mid = (l + r) >> 1;             int y = check(mid, i);             if (y)             {                    r = mid - 1;                     mi = mid;             }             else                 l = mid + 1;         }         printf("%d ", mi);     }     return 0; }

我们将b[x]代表大于x的总人数；

最开始有一次循环b[a[i]-1]++，表示大于a[i]的数+1；

第一次差分（从后往前）：b[i]代表大于i的数有多少个；

第二次差分（从后往前）：b[i]代表大于i总共有多少。

.#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<math.h> #include<unordered_map> #include<map> using namespace std; typedef long long LL; #define per(i,a,b) for(int i=a;i<=b;i++) #define ber(i,a,b) for(int i=a;i>=b;i--) const int  N = 1e6 + 100; int n, k, m, mi; int  a[N], x, b[N];  int check(int x, int i) {     int y=b[x];     if (a[i] > x)         y -= (a[i] - x);     return y<=k; } int main() {     scanf("%d%d%d", &n, &m, &k);     per(i, 1, n)     {         scanf("%d", &x);         a[x]++;     }     per(i, 1,m)         b[a[i]-1]++;     ber(i, n, 0)         b[i] += b[i+1];     ber(i, n, 0)         b[i] += b[i+1];     int l, r, mid;     per(i, 1, m)     {         if (n< k + a[i])         {             printf("-1 ");             continue;         }         l = 0;         r = n - k- a[i];         mi = -1;         while (l <= r)         {             mid = (l + r) >> 1;             int y = check(mid, i);             if (y)             {                 r = mid - 1;                 mi = mid;             }             else                 l = mid + 1;         }         if (mi == -1) printf("-1 ");         else printf("%d ", mi);     }     return 0; }