自动搬运

查看原文

来自洛谷，原作者为

	哦哟筷子 梦魂惯得无拘检，又踏杨花过谢桥。

搬运于2025-08-24 21:19:56，当前版本为作者最后更新于2018-12-16 22:40:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

现在是扯淡时间：

这是本蒟蒻第一次发题解，那么我这么垃圾为什么还要发题解呢

其实是我看这道题实在是太简单了，居然出现在BOSS区

其实是因为我看题解里的大佬实在是太大佬了，想找一个简单的办法解决这个问题

$update$ : 我写这篇题解也差不多快一年了，中间有很多评论我都没有回复，现在统一更新一下。首先声明一下，我写这篇题解的时候，刚入门，以为$AK$新手村已经很不错了，所以这话说的特别蠢（逃），而且似乎试炼场会被在不久的将来撤下，那这个话的起源都不知道去哪里了$233$.

好了，扯淡扯完了

可以恢复正题了（我觉得我这个程序应该是题解里最短的了（小声BB））

$update$:显然这样的程序并不是最短的，评论已经有很多的$dalao$指出了，而且时间复杂度也并不优秀，但是当时就会有一种莫名的自信 至于怎么压行，评论区也说得比较明白了，所以评论不用再提供压行思路了

废话不多说，先上代码

#include <bits/stdc++.h>
using namespace std; 
int main() {
	int n,k=1;
	cin>>n;
	while (n>k) {
		n=n-k;
		k++;
	}
	if(k%2==0) cout<<n<<"/"<<(k+1-n);
	else cout<<k+1-n<<"/"<<n;
	return 0;
} 

（从这一行往下全是$update$）

$update$: 首先我们观察到第$i$行，第$j$列的数就是$i/j$,这是第一个要发现的。

因为题目中要求是以$Z$字型编号

我们看题目中的表是：

$1/1,1/2,1/3$ ……

$2/1,2/2,2/3$ ……

$Z$字型编号以后（把头向左偏45度）：

第一行：$1/1$ ($1$号)

第二行：$1/2$ ($2$号) $2/1$($3$号)

第三行：$1/3$ ($6$号) $2/2$ ($5$号) $3/1$ ($4$号)

$\uparrow$ 观察法易得每一行比上一行多1

代码里那个$while$循环，就是为了通过循环枚举，判断它在编号之后的第几行，第几个位置。

（这个优化有没有都可以$AC$本题，但是评论指出我的时间复杂度不够优秀，因此提一提这个优化，不愿意看的可以直接略过看下一个分割线以后的内容。）

但其实可以直接出结论优化时间复杂度从$O(n)$ 优化到$O(1)$，这样就要考虑到等差数列求和

公式：$S=\frac{n(a_n+a_1)}{2}$

所以，很显然$Z$字型排序之后，第$k$行的数编号$n$满足：

$\frac{k(k-1)}{2} < n \le \frac{k(k+1)}{2}$

这样就可以把那个循环优化掉。代码就不贴了 （因为懒，还怕出错）

但当时我才刚学，没想到上面的这个优化（罪恶之源：我太蒻了），只好写了个丑陋的模拟233。

代码当中$k$用来记$Z$字型编号之后的行数，显然第$k$行有$k$个数，因此每次$n$要减去$k$。

最后用$k$判断奇偶，是判断这一行$Z$字型编号是正序（类似第二行）还是倒序（类似第三行）然后用最开始的结论输出原表中的行号除以列号就行了

最后，我只想表达一下自己那么蒟蒻在这里发题解的愧意

还有有问题的话大佬一定要指出！！（害怕）