2019年CSP-X复赛真题及题解（T4：金币）-171主机测评

2019年CSP-X复赛真题及题解（T4：金币）

题目描述

乔治在梦中来到了一个神奇部落，这个部落的神树具有奇特的功能：对于每一位新朋友，都会获赠金币，而且金币的数量会随时间的延续而增加：

第
第
第
……

请问：至少多少天，乔治的金币数量达到

$n$ 枚？

输入格式

一行，只有一个正整数

$n$ 。

输出格式

一行，一个整数，表示金币达到

$n$ 枚所需的最少天数。

输入输出样例 1

输入 1

输出 1

说明/提示

第

$1$ 周：每天

$1$ 枚，共

$7$ 枚；

第

$2$ 周：每天

$2$ 枚，共

$14$ 枚；

第

$3$ 周：每天

$3$ 枚，

$3$ 天即可：

7+14+3\\times 3=30

$7 + 14 + 3 \times 3 = 30$ 。

共计：

7+7+3 = 17

$7 + 7 + 3 = 17$ 天。

对于

30\\%

$30%$ 的数据，

$n$ 不超过

2147483647

$2147483647$ ；

对于

100

100\\%

$100%$ 的数据，

$n$ 的位数不超过

$18$ 。

思路分析

第 i 周每天给 i 枚金币，一周 7 天，故第 i 周总数为 7*i。
前 k 周累计金币数 $\\times (1+2+\\cdots+k)=\\frac{7k(k+1)}{2} S(k)=7×(1+2+⋯+k)=27k(k+1)，随 k 单调递增。$
二分查找最小的完整周数 k，使得 S(k) ≥ n。
前 k-1 周获得 pre = S(k-1)，还差 need = n – pre 枚。
第 k 周每天给 k 枚，补齐所需天数为 ceil(need / k)。
总天数 = 7*(k-1) + ceil(need/k)。

代码实现

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

typedef long long ll;
ll n;

ll S(ll k) { // 前k周总金币数
return 7 * k * (k + 1) / 2;
}

int main() {
cin >> n;
ll l = 1, r = 1e9, k = 0; // 二分下界1，上界1e9，k用于存储答案周数

while (l <= r) { // 二分查找第一个满足S(m)>=n的m
ll m = (l + r) / 2; // 中间值
if (S(m) >= n) { // 前m周已经够数
k = m; // 记录当前可行答案
r = m – 1; // 尝试更小的周数
} else { // 不够，需要更多周
l = m + 1;
}
}

ll p = 7 * (k – 1) * k / 2; // 前k-1周总和
ll need = n – p; // 还差多少枚金币
ll x = (need + k – 1) / k; // 第k周所需天数，ceil(need/k)通过整数上取整实现
ll d = 7 * (k – 1) + x; // 总天数 = 完整周天数 + 最后不足一周的天数

cout << d ; // 输出答案
return 0;
}

功能分析

正确性

二分确保 k 为第一个使 S(k) ≥ n 的完整周数，因此前 k-1 周金币数严格小于 n，剩余 need 必须由第 k 周补齐。
ceil(need/k) 给出补够所需的最少天数，总天数即为最优解。

时间复杂度

二分范围为 [1, 1e9]，每次判断 O(1)，总比较次数约 30 次，非常快。

空间复杂度

仅使用数个 ll 变量，O(1)。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

在这里插入图片描述

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转在这里插入图片描述 https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解： https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

在这里插入图片描述

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

在这里插入图片描述

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

在这里插入图片描述 GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}

在这里插入图片描述

2019年CSP-X复赛真题及题解（T4：金币）