dtoj#4179. 排行（rank）

阳光穿透心脏的1/2处 2022-01-07 09:17 73阅读 0赞

### 题目描述： ###

传说在2345年，Byteland中举行了一场质因数分解比赛，规则中说名次为1,2,3的参赛者将获得奖金。比赛顺利结束了，但是选手们发现主办方进行了暗箱操作，他们将选手从一个整数a<1开始排名，所以选手的名次为a,a+1,a+2...0,1,2,3 ...，也就是说拿到奖金的并不是真正的前三名。虽然选手怨声载道，主办方坚称比赛公平公正。

今年是3345年，你打算还原千年前这场比赛的名次，但是主办方称由于技术原因排名遗失了，连用于排名的a也丢失了。所幸，在Byteland中生活的都是机器人，所以你可以询问这些千年前的参赛选手。为了谨慎起见，你可以每次询问一个参赛者，某一个参赛者的比赛成绩比它好还是比它差。但是，机械心理学家告诉你，这些选手不一定愿意回答你的提问。

具体地：

名次小于1的选手由于耿耿于怀，如果它应该回答另一个参赛者成绩比它好，它就会选择不回答，否则它会如实回答。

名次为1的选手决定闷声大发财，它无论如何都不会回答任何提问。

名次为2的选手只当询问排名为3的选手时才回答比排名3的好，其他时候都不回答。

名次为3的选手趾高气扬，如果它应该回答另一个参赛者成绩比它好，它就会选择不回答，否则它会如实回答。

名次大于3的选手感觉自己水平不行，如果它应该回答另一个参赛者成绩比它差，它就会选择不回答，否则它会如实回答。

1<=n<=1000，你需要在11500次询问内还原每个选手的名次。

### 思路: ###

总结对于x<1的会对于比他大的如实回答，x>3的会对比他小的如实回答，还有2问3有回答，其余都是不回答。于是我们可以先用2\*n次询问找出最小的数以及x>3的数。

我们把不是x>3的数进行二分排序，最后三个数就是123，接下来在两两枚举这三个数，确认每个数分别对应哪个名次。

在同理把x>3的也二分排序一下。

询问次数是2\*n+nlogn+6。时间效率是n2

### 以下代码： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include "rank.hpp"
    #define il inline
    using namespace std;
    const int N=1005;
    vector<int> ans;
    bool f[N];
    int h[N],a[N],tot,b[N];
    il int Min(int x,int y){
        char c1=ask(x,y),c2=ask(y,x);
        if(c1=='g')f[x]=1;if(c2=='g')f[y]=1;
        if(c1=='b'||c2=='g')return x;
        return y;
    }
    il void ins1(int x){
        int l=1,r=tot;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(ask(a[mid],x)=='b')l=mid;
            else r=mid-1;
        }
        for(int i=tot;i>=l+1;i--)a[i+1]=a[i];
        a[l+1]=x;tot++;
    }
    il void ins2(int x){
        int l=1,r=tot;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(ask(x,a[mid])=='g')l=mid;
            else r=mid-1;
        }
        for(int i=tot;i>=l+1;i--)a[i+1]=a[i];
        a[l+1]=x;tot++;
    }
    vector<int> work(int n){
        int x=0;
        for(int i=1;i<n;i++)x=Min(x,i);
        a[1]=x;tot=1;
        for(int i=0;i<n;i++){
            if(i==x||f[i])continue;
            ins1(i);
        }
        bool pd=0;
        for(int i=tot-2;i<=tot;i++){
            for(int j=tot-2;j<=tot;j++){
                if(i!=j&&ask(a[i],a[j])=='b'){
                    b[a[i]]=2;b[a[j]]=3;x=a[j];
                    pd=1;break;
                }
            }
            if(pd)break;
        }
        for(int i=tot-2;i<=tot;i++)if(!b[a[i]])b[a[i]]=1;
        for(int i=1;i<tot-2;i++)b[a[i]]=i-tot+3;
        tot=1;a[1]=x;
        for(int i=0;i<n;i++){
            if(f[i])ins2(i);
        }
        for(int i=2;i<=tot;i++){
            b[a[i]]=i+2;
        }
        for(int i=0;i<n;i++)ans.push_back(b[i]);
        return ans;
    }

转载于:https://www.cnblogs.com/Jessie-/p/10416024.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/2b3eb5e5d4884b10a41961a2e102b212.png