解题思路:
S
第一种思路,就是暴力求解,根据题目给出的规律,很容易用O(n)的时间求出1*10^6的数据,这样就已经获得30%的分数了,再往后就会超时。
第二种思路,g[]数据表示相应的下标出现的次数,那我们可以对g[]数组求和。在求和的过程中判断求出的与目标数据的相比的大小。如果累加的和已经大于目标数据n,则求解的数字就是当前的i,这一部分核心代码如下:
for(int i=1;i<=1000000;i++){
s+=g[i];
if(s>=n)
cout<<i;
}
但是这一种方法需要刚才第一种方法提供的数据,因此计算出的数据范围受第一种是方法范围的影响,只能完成10^9左右的数据。也就是70%的数据。
第三种,因为第i个数据会在g[]数组中出现g[i]次,那么那么就相当于在g[]数组中会出现g[i]段长度为i且这i个数字相等的数字段,这样的话,就可以根据n在那一个数字段中求解。实现代码如下:
for(int i=1;;i++){
s+=i*(LL)g[i];
if(s>=n){
.....
}
}
如果将n确定在第i个数据段,那么需要将前i-1个数据段包含的数据相加。每个数据段包含g[]数据,则相当对数组g前i-1项求和。
n在第i个数据段中,是第n-m个数字。在第i个段中,每一个数据会重复i次。那么n-m就是在这个段中的位置就是roundup((n-m)/i)。因为在c++中没有向上取整,但是有个取整公式roundup((n-m)/i)==rounddown((n-m+i-1)/i).核心代码如下:
for(int i=1;;i++){
s+=i*(LL)g[i];
if(s>=n){
s-=i*(LL)g[i];
cout<<t+(n-s+i-1)/i;
break;
}
t+=g[i];
}
注意事项:
参考代码:
#include"iostream"
using namespace std;
typedef long long LL;
const int N=1000010;
int g[N];
int main(){
g[1]=1,g[2]=2;
for(int i=2,j=2;i<N;i++){
for(int k=0;k<g[i]&&j<N;k++)
g[j++]=i;
}
LL s,n,t;
cin>>n;
s=t=0;
for(int i=1;;i++){
s+=i*(LL)g[i];
if(s>=n){
s-=i*(LL)g[i];
cout<<t+(n-s+i-1)/i;
break;
}
t+=g[i];
}
return 0;
}
0.0分
15 人评分
C语言程序设计教程(第三版)课后习题8.9 (C语言代码) 用函数传参的方法浏览:4063 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:516 |
不容易系列 (C语言代码)浏览:660 |
printf基础练习2 (C语言代码)浏览:940 |
WU-字符串比较 (C++代码)浏览:753 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:2085 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:542 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:681 |
C二级辅导-公约公倍 (C语言代码)浏览:481 |
分糖果 (C语言代码)浏览:910 |