題目鏈接：點擊查看

題目大意：第一行給出兩個數(shù)n和m，n代表有n個數(shù)，m代表有m組比較關系，接著給出m組關系pos_a和pos_b，代表在一個數(shù)組中，pos_a和pos_b存在一種比較關系

現(xiàn)在要求我們構造出兩個數(shù)組，要求是：

第一個數(shù)組是1~n的一種全排列

第二個數(shù)組只有兩個數(shù)字是重復的，其余的數(shù)字從1~n中取值

第一個數(shù)組和第二個數(shù)組的比較關系必須保持一致

題目分析：這個題目的第三點要求比較難看懂，舉個例子吧，我們現(xiàn)在的給出兩組關系，1 2和2 3，現(xiàn)在構造出的數(shù)組1是：1 3 2，那么第一個數(shù)和第二個數(shù)的關系是pos_1<pos_2，第二個數(shù)和第三個數(shù)的關系是pos_2>pos_3，我們接下來需要構造的數(shù)組需要滿足除了上面的第二個條件之外，還需要滿足pos_1<pos_2以及pos_2>pos_3，所以我們可以隨意構造出滿足條件的一種，比如1 3 1，那么現(xiàn)在大概應該能摸清楚這個題目的大體意思了，接下來該想一下怎么構造通項，也就是可以滿足所有式子的一種構造方法，我們首先想一下答案為NO的情況，也就是無法構造的情況，因為現(xiàn)在有n個數(shù)，若兩兩之間產生關系的話，最多有n*(n-1)種關系，又因為這個題目提前說明了沒兩個位置的關系至多給一次，所以可以當做有向邊來處理，也就是最多會有n*(n-1)/2種關系就可以確定唯一的一個數(shù)組了，所以當m大于等于n*(n-1)/2的時候是無解的，現(xiàn)在我們繼續(xù)討論有解的情況，如果題目給出的對應關系m小于等于n*(n-1)/2的話，那么必定至少可以找出一組的兩個位置沒有對應關系，那么我們在這兩個位置上進行操作就好了，對于數(shù)組1，我們在這兩個位置上放上最大值和次大值，或者最小值或次小值，然后在第二個數(shù)組上都放上最大值或最小值或次大值或次小值都可以，只要對應起來就可以了，這樣其余有關系的位置上，兩個數(shù)組的值都一模一樣了，對應關系也肯定都滿足，這樣構造出來的答案就可以滿足通項了

對于這個題目，我是選擇用最大值和次大值來構造的，具體實現(xiàn)來看代碼吧

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m;pair<int,int>a[N];pair<int,int>find() {int cnt=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(make_pair(i,j)!=a[++cnt]){return make_pair(i,j);} }int main() { // freopen("input.txt","r",stdin);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int num1,num2;scanf("%d%d",&num1,&num2);a[i]=make_pair(min(num1,num2),max(num1,num2));//保存所有的對應關系，讓較小的下標在前面}if(m>=n*(n-1)/2)//特判return 0*printf("NO\n");printf("YES\n");sort(a+1,a+1+m);//對于所有關系排序pair<int,int>pos=find();//隨便找一個沒有對應關系的兩個位置int cnt=0;for(int i=1;i<=n;i++){if(i==pos.first)//在某個位置上放最大值printf("%d ",n);else if(i==pos.second)//另一個位置上放次大值printf("%d ",n-1);elseprintf("%d ",++cnt);}printf("\n");cnt=1;for(int i=1;i<=n;i++){if(i==pos.first)//都放上最大值或次大值printf("%d ",n);else if(i==pos.second)//同上printf("%d ",n);elseprintf("%d ",++cnt);}return 0; }

代碼：

?

總結

以上是生活随笔為你收集整理的CodeForces - 1090D Similar Arrays(构造+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。