文章

211

粉丝

1

获赞

1151

访问

42.1k

头像
缺页问题 题解:二分
P1506
发布于2026年3月9日 12:26
阅读数 117

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> books(n);
	for(int i=1;i<n;i++)
		cin >> books[i];
	sort(books.begin(),books.end());
	
     // 二分查找:第一个 books[i] != i 的位置
    int left = 1, right = n, ans = n + 1;  // 默认缺失n+1
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (books[mid] != mid) {  // 缺失在左边或当前位置
            ans = mid;  // 缺失的数字是 mid
            right = mid - 1;  // 继续向左查找
        } else {
            left = mid + 1;  // 前半部分完整,向右查找
        }
    } 
    cout << ans << endl;
	return 0;
}	

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发