题目链接：点击查看

题目大意：先给出一个长度为n的序列ai，这个序列是1~n全排列中的其中一种，再给出一个n*n的矩阵，maze[i][j]=val代表min(ai,aj)=val，要求我们构造出原始序列ai

题目分析：其实仔细观察一下给出的样例我们就可以发现：

若当前位置应该是1的话，那么当前的一行除了0之外就全是1了（因为1是最小的数字）

若当前位置应该是2的话，那么当前的一行除了0之外，有一个1，其余的都是2了

若当前位置应该是3的话，那么当前的一行除了0之外，有一个1，一个2，其余的都是3了

以此类推下去，我们就会发现对每一行的权值和排一下序就能得到原序列的位置了，实际上除了n和n-1所在的两行他们的数字表示的都一样之外，其余的数字的位置都是固定的

上面是一种方法，还有一种方法，我相信继续观察一下也是可以看出来的，再看一下上面的那三句话，我们就可以直接得出结论：

当前位置所代表的数，就是当前行中的最大值（除了n和n-1，因为他们两行的最大值都是n-1），这样一来我们只需要对这两行特判一下即可，然后实现就好了

代码：

方法一：权值和排序

#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> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;struct Node {int id,val;bool operator<(const Node& a)const{return val<a.val;} }a[N];int ans[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){a[i].id=i;for(int j=1;j<=n;j++){int num;scanf("%d",&num);a[i].val+=num;}}sort(a+1,a+1+n);for(int i=1;i<=n;i++)ans[a[i].id]=i;for(int i=1;i<=n;i++)printf("%d ",ans[i]);return 0; }

方法二：找最大值

#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> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;int ans[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int mmax=-1;for(int j=1;j<=n;j++){int num;scanf("%d",&num);mmax=max(mmax,num);}ans[i]=mmax;}for(int i=1;i<=n;i++)if(ans[i]==n-1){ans[i]=n;break;}for(int i=1;i<=n;i++)printf("%d ",ans[i]);return 0; }

 

超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的CodeForces - 618B Guess the Permutation(思维+构造)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。