专栏文章
P10451 Innovative Business 题解
P10451题解参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @miqdiwna
- 此快照首次捕获于
- 2025/12/04 03:02 3 个月前
- 此快照最后确认于
- 2025/12/04 03:02 3 个月前
题目描述
有 个元素,你需要询问形如
? a b 这样的问题(不超过 个),获得元素 和元素 的大小关系,并按元素升序排序把 个元素输出。。
分析
假设我们已经把前 个元素按升序排序,那么对于第 个元素,我们显然可以把它插入到前 个元素中,使得前 个元素为升序排序。
考虑二分当前序列中第一个大于第 个元素的元素编号,并把第 个元素查到该元素的前面,即可使得前 个元素为升序排序。
因为确定每个元素的位置仅需查询 次,所以总询问次数大约为 ,又因为 ,所以 ,故可通过本题。
代码
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 条评论,欢迎与作者交流。
正在加载评论...