[大数据]洛谷P1014

题目介绍

洛谷P1014自己去洛谷看一下。

思路

就真的是傻傻地来模拟地，还用了一个flag来考虑转弯。

AC代码

至于为什么要在p那加50，是因为试了很多次大数据过不了的原因 。
可以过本题n≤10⁷。就可能这样做的有点傻（大佬勿喷）

#include <bits/stdc++.h>
using namespace std;
string s[2000][2000];
int main() {
	int n;
	cin >> n;
	int p;
	for (int i = 1; i < ((int) sqrt(n)) + 1; i++) {
		if (i * i == n) {
			p = i;
		} else if (i * i < n && (i + 1) * (i + 1) > n) {
			p = i + 1;
		}
	}
	for (int i = 0; i < p + 50; i++) {
		for (int j = 0; j < p + 50; j++) {
			s[i][j] = to_string(i + 1) + '/' + to_string(j + 1) ;
		}
	}
	int x = 0, y = 0, flag = 1;
	for (int i = 0; i < n - 1; i++) {
		switch (flag % 4) {
			case 1:
				y++;
				break;
			case 2:
				x++;
				y--;
				break;
			case 3:
				x++;
				break;
			case 0:
				x--;
				y++;
				break;
		}
		if (x == 0) {
			flag++;
		} else if (y == 0 && x != 0) {
			flag++;
		} else if (flag == 3) {
			flag++;
		} else if (flag == 4 && x == 0) {
			flag++;
		}
	}
	cout << s[x][y];
}

改进

如图，以斜对角线来看，对于第i条来说每个分数的分子分母之和都是i+1。而且前i条对角线的个数为(i+1)*i/2个。所以如果给定一个n的话，我们可以通过二分来查找n在哪条对角线上，并确定是这条对角线的第几个元素。这样一来复杂度就变成O(logn)就简单多了。
为什么要用二分：因为同样是查找，用二分效率更高。前面一种算法也可以用二分法。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, r, l = 1, mid;
	cin >> n;
	r = n;
	while (r > l) {
		int mid = (r + l) / 2;
		if (mid * (mid + 1) / 2 < n)
			l = mid + 1;
		else
			r = mid;
	}
	//查找出来的r或者l就是n所在的斜对角线 这个是相等就退出
	int a = n - l * (l - 1) / 2; //该数在第mid条斜对角线排第几个
	//奇偶不同 数字的升降不同
	if (l % 2 == 0)
		cout << a << '/' << l + 1 - a;
	else
		cout << l + 1 - a << '/' << a;
}