参考文章
题意
题目表述的很清楚
思路
#1 暴力枚举
根据题目给出的规律,很容易用 O ( n ) O(n) O(n) 的时间求出 1 0 6 10^6 106 的数据,这样就可以得到 30 30 30 分。
显然,这种方法是不对的,我们在上面进行优化。
#2 枚举优化
gig_igi 用来表示对应下标出现的次数,先对 g i g_i gi 求和 ∑ i = 1 n g i \sum_{i=1}^{n} g_i ∑i=1ngi。在求和的时候判断与目标数据的大小。如果大于目标 n n n,则答案就是下标 i i i。
这样可以得到 70 70 70 分。
#3 正解
因为第 i i i 个数据会在 g g g 中出现 g i g_i gi 次,那么那么就相当于在 g g g 中会出现 g i g_i gi 个长 i i i 且数字相等的区间,这样的话,就可以根据 n n n 所在的区间去求解。
推断出 n n n 在第 i i i 个数据段中,是第 n − m n - m n−m 个数字。在第 i i i 个区域中,每一个数据会重复出现 i i i 次。那么 n − m n-m n−m 就是在这个段中的位置就是 ⌈ ( ( n − m ) / i ) ⌉ \left \lceil ((n - m) / i) \right \rceil ⌈((n−m)/i)⌉。
这样可以得到 100分。
代码
#include <bits/stdc++.h>
#define int long long // 定义int为long long类型,便于处理大数
using namespace std;
int n, res, cnt, g[1000010];
int main() {
ios :: sync_with_stdio(false); // 关闭同步,提高输入输出效率
cin >> n; // 读取输入的n值
g[1] = 1, g[2] = 2; // 初始化g数组的前两个元素
// 预处理 g[i] 数组
for (int i = 2, j = 2; i < 1000010; i++)
for (int k = 0; k < g[i] && j < 1000010; k++) g[j++] = i;
int i = 1;
while (true) {
res += i * g[i]; // 计算当前总和
if (res >= n) // 如果总和大于等于n,计算并输出结果
return res -= i * g[i], cout << cnt + (n - res + i - 1) / i << endl, 0;
cnt += g[i++]; // 计数器增加
}
return 0;
}