2、卡片
题目 卡片
思路分析
一张卡片只有 11 一种分法 （1）
两张 11 12 22 三种 （1+2）
三张 11 12 13 22 23 33 六种 （1+2+3）
……（1+2+……+n)
所以呈现等差数列的性质
因为它说给的数据在1e9内 所以尽可能构造出到八位的所有项
给定一个n 要能分得出n个人 就必须大于等于n
所以在构造出的序列中 二分出 第一个大于n的数 下标就是需要的卡片数
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main()
{
int n;cin>>n;
for(int i=1;i<10000;i++){
a[i]=1+(i-1);
s[i]=s[i-1]+a[i];
// cout<<s[i]<<" ";
}
int l=1,r=10000;
while(l<r){
int m=l+r>>1;
if(s[m]>=n)
r=m;
else
l=m+1;
}
cout<<r;
return 0;
}
傻逼了 只需要在构造的时候 看什么时候满足n就停止即可
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main()
{
int n;cin>>n;
for(int i=1;;i++){
a[i]=1+(i-1);
s[i]=s[i-1]+a[i];
if(s[i]>=n){
cout<<i;
return 0;
}
}
return 0;
}
💬 评论