Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用int会TLE,用long long int就ac,估计是因为int爆了之后二分出现上界小于下界所以死循环了

Posted by KatrineYang at 2016-07-05 17:55:51 on Problem 1064 and last updated at 2016-07-05 17:58:37
//============================================================================
// 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator