| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
用int会TLE,用long long int就ac,估计是因为int爆了之后二分出现上界小于下界所以死循环了//============================================================================
// Name : main1064.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
using namespace std;
long long int cables[10001];
long long int N, K;
long long int truncate(long long int n, long long int k){
if(n >= k) return n-k;
return 0;
}
bool isOK(long long int r){
long long int sum = 0;
for(long long int i = 0; i < N; i++){
sum += cables[i]/r;
}
return sum >= K;
}
long long int binary(long long int low, long long int up){
if(up - low == 1) return low;
long long int middle = (low + up)/2;
if(isOK(middle)){
return binary(middle, up);
}
else{
return binary(low, middle);
}
}
int main() {
//int N, K;
cin >> N >> K;
long long int sum = 0;
//bool zc = true;
for(long long int i = 0; i < N; i++) {
long long int zs;
char dian, shifen, baifen;
//double temp;
cin >> zs >> dian >> shifen >> baifen;
cables[i] = zs * 100 + (shifen-'0') * 10 + (baifen-'0');
//cout << cables[i] << endl;
sum += cables[i];
//if(cables[i]%)
//int mx, mn;
}
long long int mx, mn;
mx = sum / K;
long long int i_sum = 0;
for(long long int i = 0; i < N; i++) i_sum += truncate(cables[i], mx);
mn = i_sum / K;
//cout << mn << " " << mx << endl;
long long int res = binary(mn, mx+1);
//cout << res << endl;
printf("%.2lf", (res / 100.0));
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator