专栏文章

P10451 Innovative Business 题解

P10451题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqdiwna
此快照首次捕获于
2025/12/04 03:02
3 个月前
此快照最后确认于
2025/12/04 03:02
3 个月前
查看原文

题目描述

nn 个元素,你需要询问形如 ? a b 这样的问题(不超过 1000010000 个),获得元素 aa 和元素 bb 的大小关系,并按元素升序排序把 nn 个元素输出。
1n10001 \le n \le 1000

分析

假设我们已经把前 kk 个元素按升序排序,那么对于第 k+1k+1 个元素,我们显然可以把它插入到前 kk 个元素中,使得前 k+1k+1 个元素为升序排序。
考虑二分当前序列中第一个大于第 k+1k+1 个元素的元素编号,并把第 k+1k+1 个元素查到该元素的前面,即可使得前 k+1k+1 个元素为升序排序。
因为确定每个元素的位置仅需查询 logn\log n 次,所以总询问次数大约为 nlognn \log n,又因为 1n10001 \le n \le 1000,所以 nlogn10000n \log n \le 10000,故可通过本题。

代码

CPP
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> v;
bool compare(int a,int b){
	cout<<"? "<<a<<' '<<b<<endl;
	bool t;
	cin>>t;
	return t;
}
int main(){
	cin>>n;
	v.push_back(1);
	for(int i=2;i<=n;i++){
		int l=0,r=v.size();
		while(l<r){
			int mid=l+r>>1;
			if(compare(i,v[mid]))r=mid;
			else l=mid+1;
		}
		v.insert(v.begin()+r,i);
	}
	cout<<"! ";
	for(int i=0;i<n;i++)cout<<v[i]<<' ';
	return 0;
}

评论

1 条评论,欢迎与作者交流。

正在加载评论...