終于發(fā)現(xiàn)自己G題Accelarator的錯(cuò)誤了 找了好久好久 就這個(gè)錯(cuò)誤 讓我在整個(gè)后半段的比賽中幾乎廢掉了 太不應(yīng)該了！
吸取教訓(xùn)！在場上出現(xiàn)自己無法找出錯(cuò)誤的情況 應(yīng)該要讓隊(duì)友重寫
#include <stdio.h>
#include <string.h>
#include <math.h>
const int N = 100010;
int d[N];
__int64 d2[N];
int na, av, np;
bool check(int x) {
int i;
for(i = 0; i < np; i++) d2[i] = d[i];
for(i = 0; i < np; i++) d2[i] -= x;
int cnt = 0;
__int64 rest = na*x; 左邊寫了__int64 右邊卻忘記轉(zhuǎn)成__int64了
for(i = 0; i<np; i++) {
if(d2[i] > 0) {
if(av <= 0) return false;
__int64 need = (d2[i]-1)/av + 1;
if(need > rest || need > x) return false;
rest -= need;
}
}
return 1;
}
int main() {
int ntc, i;
scanf("%d", &ntc);
while(ntc--) {
scanf("%d", &np);
int _max = -1;
for(i = 0; i<np; i++) {
scanf("%d", d + i);
if(d[i] > _max) _max = d[i];
}
scanf("%d %d", &na, &av);
av--;
int lo = 0, hi = _max;
while(lo < hi) {
int mid = lo + (hi-lo)/2;
if(check(mid)) hi = mid;
else lo = mid+1;
}
if(check(lo)) printf("%d\n", lo);
}
return 0;
}
Accelerator
Time Limit:4000MS Memory Limit:65536K
Total Submit:811 Accepted:142
Description
Shiming (alpc02) is a boy likes to play PopKart very much. He is a good rider in this game. And one day he thought that he became a team leader of a team of N Kart riders.
Today, after the game begins, the riders of his team are now at different places at the racetrack, for that some of the riders got some short cut.
However, we know actually how long has each rider left to run along, and they will ride actually one meter per one time unit (maybe 10ms).
Luckily, Shiming now gets M accelerators, the accelerator can help one rider to ride k meters per one time unit. And all the accelerators are as the same. But one rider can't use more than one accelerator at one time unit.
Shiming is the team leader, and he wants all the team members to finish in the minimal time not just the fastest one to finish the race. He will distribute all the accelerators to the riders.
Note: Here some rules are not as the same as the game we played. At a time unit, Shiming distributes the accelerators to riders for one rider one accelerator, and at the next time unit, all the accelerator can be reused, and Shiming can re-distributes all the accelerators to riders also for one rider one accelerator and the distribution is no relationship with the last time unit.
So you will program to help Shiming to get the actually minimal time the team will use to finish the race.
Input
The input file has T (1<T<20) test cases, and the first line of the file will show the T.
Each of test cases, will be the N (1<= N <= 100000) rider, and N numbers Ai (1<= Ai <= 10^8) show how long will the rider have to finish the race. And the M and the K (1<= K*M <=10^8) for the accelerators.
Output
For each of test cases print a single integer on a single line, the minimal possible number of time units required to finish the race all team.
Sample Input
2
3
2 3 9
1 5
3
2 3 6
1 5
Sample Output
3
2