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

47ms 秒过 贴代码

Posted by hzoi_hexing at 2014-04-17 19:46:25 on Problem 2456 and last updated at 2014-04-17 19:46:35
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 101000
int n,c;
int a[N];

bool check(int x){
	int p = a[1];
	int t = 1;
	for (int i = 2; i <= n; i++){
		if (a[i] - p >= x){
			t ++;
			p = a[i];
		}
	}
	return t >= c;
}

inline int getint(){
	char ch;
	int x = 0;
	while (!isdigit(ch = getchar()));
	x = ch - 48;
	while (isdigit(ch = getchar())) x = x * 10 + ch - 48;
	return x;
}

int main(){
	n = getint(); c = getint();
	for (int i = 1; i<=n; i++) a[i] = getint();
	sort(a + 1,a + 1 + n);
	int l = 0,r = 1000000001;
	int ans;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1,ans = mid;
		else r = mid - 1;
	}
	printf("%d\n",ans);
}

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