D题 二分答案能写不
有大佬帮忙看看这二分的哪里有问题吗?😶🌫️
// Problem: 快来帮芙芙吧* II // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/99073/D // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) // Problem: 快来帮芙芙吧* I // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/99073/C // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> typedef long long ll; // 确保 ll 在使用前被定义 using namespace std; ll n,k; bool check(ll mid) { // 这个即 x // 如果 mid < left right > mid how to 二分答案 //假如 x 满足条件 //x-1 > x < x + 1 //我需要检查当前这个值是否大于 int lefts = 0,mids = 0, rights = 0; for(int i = 1; i <= n; i++) { mids += min(1ll*abs(i - mid), 1ll * abs(i - mid - k)); lefts += min(1ll*abs(i - mid + 1), 1ll * abs(i - mid - k + 1)); rights += min(1ll*abs(i - mid - 1), 1ll * abs(i - mid - k - 1)); } // left < mid ? right > mid // ans == mid // mid > left mid < rgiht // r = ZZ if(rights > mids && mids < rights) return false; else return true; } void solve(){ std::cin >> n >> k; //for(ll i = 1; i <= n ; i++) std::cin >> a[i]; ll l = 1, r = n; while(l + 1 != r) { ll mid = (l + r) >> 1; if(check(mid)) l = mid; else r = mid; } std::cout << l << "\n"; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int T = 1; std::cin >> T; for(int i= 1; i <= T; ++i) solve(); return 0; }