【最少刷题数——二分】

1.最少刷题数 - 蓝桥云课 (lanqiao.cn)

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 15e4+10;
int a[N];
int le[N], e[N]; //le表示less or equal e表示equal
int n;
bool check(int i, int x)
{return n - le[x] <= le[x] - (e[x] + (a[i] != x ? 1 : 0)); //若a[i] + mid = x，则e[x]要增加1
}
int main()
{cin >> n;for(int i = 1; i <= n; i++)cin >> a[i], e[a[i]]++;le[0] = e[0];for(int i = 1; i <= 1e5; i++){le[i] = e[i];le[i] += le[i-1];}for(int i = 1; i <= n; i++){int l = 0, r = 1e5;while(l < r){int mid = l + r >> 1;if(check(i, a[i] + mid)) r = mid;else l = mid+1;}cout << l << ' ';}
}