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;
}

全部评论

相关推荐

积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务