首页 > 代码库 > Codeforces Round #418 B

Codeforces Round #418 B

2024-10-14 02:54:39   216人阅读

An express train to reveries

题意：给2长度为n的数列a b，a b中至少存在一个i使得ai！=bi，构造一个数列p，使得恰好存在一个i使得ai！=pi，且恰好存在一个j使得aj！=pj，且p里面的数为1-n且无重复，输出p，保证有解

思路：题目保证有解，可知，最多存在2个i使得ai！=bi，最少一个，如果只有一个，那么好办，令p=a，将pi换成1-n中没有出现的那个数就可以了，如果有存在2个不等的数，那么令p=a（除开两个ai！=bi的位置），找出未出现的2个数，将2个数分别放在ai！=bi的位置上，判断一下是否满足要求（使得恰好存在一个i使得ai！=pi，且恰好存在一个j使得aj！=pj），若满足输出答案，若不满足，则调换2个数的位置，此时一定满足，输出答案

AC代码：

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int N=1e5+100;
int a[1005],b[1005],p[1005],mp[1005],n,mk1,mk2,k1,k2,k;
int main(){
    cin>>n;
    for(int i=1; i<=n; ++i){
        cin>>a[i];
    }
    for(int i=1; i<=n; ++i){
        cin>>b[i];
        if(a[i]!=b[i] && !mk1){
            mk1=mk2=i;
            k++;
        }
        else if(a[i]!=b[i]){
            mk2=i;
            k++;
        }
        else p[i]=a[i],mp[p[i]]++;
    }
    if(k==1){
        for(int i=1; i<=n; ++i){
            if(!mp[i]){
                p[mk1]=i;
                break;
            }
        }
    }
    else{
        for(int i=1; i<=n; ++i){
            if(!mp[i] && k1==0){
                k1=i;
                k--;
            }
            else if(!mp[i]){
                k2=i;
                k--;
            }
            if(!k) break;
        }
        p[mk1]=k1,p[mk2]=k2;
        if((p[mk1]!=a[mk1] && p[mk1]!=b[mk1]) || (p[mk2]!=a[mk2] && p[mk2]!=b[mk2])){
            p[mk1]=k2,p[mk2]=k1;
        }
    }
    for(int i=1; i<=n; ++i){
        cout<<p[i]<<" ";
    }
    return 0;
}
/*
5
1 2 3 4 3
1 2 5 4 5
5
4 4 2 3 1
5 4 5 3 1
4
1 1 3 4
1 4 3 4
*/

 

Codeforces Round #418 B


联系
我们