A题用二分求最小的数为什么不可以啊
我的做法是求数组所有合的平均数然后在区间[1,ave]之间二分,可是答案只过了百分之二十。
看了题解发现题解的做法是找到最中间的一个数的前一个数,然后再加上一。
可是这道题的性质也满足二分的性质。在[1,ave]之间找到一个满足条件的最小的数。有同学能帮我解答一下吗。
#include <iostream> #include <cstring> using namespace std; const int N = 2e5 + 5 ; typedef long long LL ; int a[N] ; LL s = 0 ; int n ; LL check(int t) { int cnt1 = 0, cnt2 = 0 ; for(int i = 0 ; i < n ; i ++) { cnt1 += a[i] < t; cnt2 += a[i] > t ; } return min(cnt1, cnt2) ; } int main() { cin >> n ; int tt = 0x3f3f3f3f ; for(int i = 0 ; i < n ; i ++) { scanf("%d",&a[i]) ; tt = min(tt, a[i]) ; s += a[i] ; } LL r = s / n ; LL l = tt ; LL value = check(r) ; while(l < r) { LL mid = l + r >> 1 ; LL v = check(mid) ; if(v == value) { r = mid ; // value = v ; }else { l = mid + 1; } } cout << value << " " << r << endl ; }