暑假训练赛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<bits/stdc++.h>
using namespace std;
vector<unsigned long long> 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;
}