题目链接:A-So I'll Max Out My Constructive Algor..._第46屆ICPC 東亞洲區域賽(澳門)(正式賽) (nowcoder.com)
如果看不到题目请先报名比赛,就可以看到了。
题目大意
给定一个规模为N * N的矩阵,每个数字表示某个位置的高度h[i][j],现在要使得每个位置都走且仅走一次(exactly once),且上升的次数比下降的次数少。
并且高度是一个[1,N * N]的排列,也就是说不会出现一样高的位置。
只要答案合理就正确。
思路
使得每个位置都走到,可以直接S形模拟走一遍,如果这样的方案上升次数比下降次数大的话,那么就反过来输出就行了。原理也比较简单,我们只需要构造合理的排列就行了。
代码
/*Copyright (C) Eriktse 2022*/ #include <bits/stdc++.h> #define int long long using namespace std; inline int readInt() { int s = 0,w = 1;char ch = getchar(); while(ch < '0' || ch > '9'){if(s == '-')w = -1;ch = getchar();} while('0' <= ch && ch <= '9')s = s * 10 + ch - '0', ch = getchar(); return s * w; } const int maxn = 70; int h[maxn][maxn]; void solve() { int N;cin >> N; for(int i = 1;i <= N; ++ i) for(int j = 1;j <= N; ++ j) h[i][j] = readInt(); //input finished int ans[maxn * maxn], pa = 0; for(int i = 1;i <= N; ++ i) { if(i & 1)for(int j = 1;j <= N; ++ j)ans[++ pa] = h[i][j]; else for(int j = N;j >= 1; -- j)ans[++ pa] = h[i][j]; } int cnt = 0;//表示升序的个数 for(int i = 2;i <= pa; ++ i)if(ans[i - 1] < ans[i])cnt ++; if(cnt > (pa - 1) / 2) for(int i = pa;i >= 1; -- i)printf("%lld%c",ans[i], i == 1 ? '\n' : ' '); else for(int i = 1;i <= pa; ++ i)printf("%lld%c",ans[i], i == pa ? '\n' : ' '); } signed main() { int T;cin >> T; while(T --)solve(); return 0; }
Comments NOTHING