暑假训练赛8--C一生之敌----Vector
Problem C: 一生之敌
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 721 Solved: 115
[Submit][Status][Web Board]
Description
Input
第一行输入一个整数T，表示数据组数。
每组数据输入一个整数n。
1 <= T <= 100000
0 <= n <= 10^19
保证结果存在
Output
输出一个整数。
Sample Input
3
2
6
100
Sample Output
6
6
114
【分析】
-
要用到vector，然后没有用栈，我觉得可能是因为栈是静态的，向量是动态的，动态存储的话比较高效。。
-
然后这道题还要对表达式进行稍稍的运算一下。b^2=2a(a+1)^2----->b=(a+1)sqrt(2a)------>因为a、b都是整数------->a=(i*i)/2-------->b=(a+1)i；
-
lower_bound(a.begin(),a.end(),n)-a.begin(); 查找有序区间中第一个大于或等于某给定值的元素的位置
-
a.push_back((x+1)*i); 这里读入数据的时候已经有序
#include
using namespace std;
vector a; //换成long long的话会超时，这里我也不是太懂为什么要用无符号整型
int main()
{int t; long long n;for(unsigned long long i=0;;i+=2) //表达式做变换后，因为是整数所以i只能每次增2而不是1{unsigned long long x=i*i/2;a.push_back((x+1)*i);//已经有序 //这里是向量读入数据的方式if((x+1)*i>1e19)break; //循环结束条件} scanf("%d",&t);while(t--){unsigned long long n;scanf("%llu",&n);int k=lower_bound(a.begin(),a.end(),n)-a.begin();//查找有序区间中第一个大于或等于某给定值的元素的位置printf("%llu\n",a[k]);// cout<<"ok\n";}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！