版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/41673007
http://codeforces.com/contest/492
A 水题
A. Vanya and Cubes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vanya got n cubes. He decided to build a pyramid from them. Vanya wants to build the pyramid as follows: the top level of the pyramid must consist of 1 cube, the second level must consist of 1 + 2 = 3 cubes, the third level must have 1 + 2 + 3 = 6 cubes, and so on. Thus, the i -th level of the pyramid must have 1 + 2 + ... + ( i - 1) + i cubes.
Vanya wants to know what is the maximum height of the pyramid that he can make using the given cubes.
Input
The first line contains integer n ( 1 ≤ n ≤ 10 4 ) — the number of cubes given to Vanya.
Output
Print the maximum possible height of the pyramid in the single line.
Sample test(s)
input
1
output
1
input
25
output
4
Note
Illustration to the second sample:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <valarray>
#include <list>
#include <stack>
#include <array>
#include <iomanip>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
using namespace std;
int n,m;
int a[1000];
int main ()
{
a[1] = 1;
for(int i=1;i<=999;i++)
a[i] = a[i-1]+i;
while (cin>>n)
{
int i =1;
int ans = 0;
while (n-a[i] >=0)
{
n-=a[i];
i++;
ans++;
}
cout<<ans<<endl;
}
return 0;
}
B 简单贪心
B. Vanya and Lanterns
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vanya walks late at night along a straight street of length l , lit by n lanterns. Consider the coordinate system with the beginning of the street corresponding to the point 0 , and its end corresponding to the point l . Then the i -th lantern is at the point a i . The lantern lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all lanterns.
Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?
Input
The first line contains two integers n , l ( 1 ≤ n ≤ 1000 , 1 ≤ l ≤ 10 9 ) — the number of lanterns and the length of the street respectively.
The next line contains n integers a i ( 0 ≤ a i ≤ l ). Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.
Output
Print the minimum light radius d , needed to light the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9 .
Sample test(s)
input
7 15
15 5 3 7 9 14 0
output
2.5000000000
input
2 5
2 5
output
2.0000000000
Note
Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of the street, and the second lantern will light segment [3, 5] . Thus, the whole street will be lit.
#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <valarray>
#include <list>
#include <stack>
#include <array>
#include <iomanip>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
using namespace std;
int n,l;
double a[1010];
int main ()
{
while (cin>>n>>l)
{
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
double ans = a[1] ;
for(int i=1;i<=n-1;i++)
{
ans = max (ans,(a[i+1]-a[i])*1.0/2);
}
ans = max(ans,l-a[n]);
printf("%.10lf\n",ans);
}
return 0;
}
C 按照bi升序排列 注意不要超时即可
C. Vanya and Exams
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vanya wants to pass n exams and get the academic scholarship. He will get the scholarship if the average grade mark for all the exams is at least avg . The exam grade cannot exceed r . Vanya has passed the exams and got grade a i for the i -th exam. To increase the grade for the i -th exam by 1 point, Vanya must write b i essays. He can raise the exam grade multiple times.
What is the minimum number of essays that Vanya needs to write to get scholarship?
Input
The first line contains three integers n , r , avg ( 1 ≤ n ≤ 10 5 , 1 ≤ r ≤ 10 9 , 1 ≤ avg ≤ min ( r , 10 6 ) ) — the number of exams, the maximum grade and the required grade point average, respectively.
Each of the following n lines contains space-separated integers a i and b i ( 1 ≤ a i ≤ r , 1 ≤ b i ≤ 10 6 ).
Output
In the first line print the minimum number of essays.
Sample test(s)
input
5 5 4
5 2
4 7
3 1
3 2
2 5
output
4
input
2 5 4
5 2
5 2
output
0
Note
In the first sample Vanya can write 2 essays for the 3rd exam to raise his grade by 2 points and 2 essays for the 4th exam to raise his grade by 1 point.
In the second sample, Vanya doesn't need to write any essays as his general point average already is above average.
#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <valarray>
#include <list>
#include <stack>
#include <array>
#include <iomanip>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
using namespace std;
int n;
long long r;
long long avg,AVE;
struct q
{
int a;
int b;
}p[100010];
bool cmp(q aa,q bb)
{
return aa.b < bb.b;
}
int main ()
{
while (cin>>n>>r>>avg)
{
AVE= 0;
for(int i=1;i<=n;i++)
{
cin>>p[i].a>>p[i].b;
AVE+=p[i].a;
}
if (AVE >= avg*n)
{
cout<<0<<endl;
return 0;
}
sort(p+1,p+1+n,cmp);
long long ans = 0;
int i = 1;
while ( AVE < avg*n )
{
ans += p[i].b * min ( r -p[i].a,n*avg - AVE );
AVE += min(r -p[i].a,n*avg - AVE);
i++;
}
cout<<ans<<endl;
}
return 0;
}
留言