ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

ICPC澳门站签到题A - So I'll Max Out My Constructive Algor...(模拟 + 构造)

2022年4月3日 862点热度 0人点赞 0条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ icpc 构造 模拟 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号