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

一道好题被数据规模毁了。。。O(nlogn)可做

Posted by KatrineYang at 2017-01-20 13:29:59 on Problem 1599 and last updated at 2017-01-20 13:34:19
思路很简单,就是排序之后补0到2C个,然后头尾配对
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;

int main() {
	int C, S;
	int cnt = 0;
	while(cin >> C >> S){
		cnt++;
		cout << "Set #" << cnt << endl;
		int *mass = new int[2 * C];
		for(int i = 0; i < 2*C; i++) mass[i] = 0;
		int sum = 0;
		for(int i = 0; i < S; i++) {
			cin >> mass[i];
			sum += mass[i];
		}
		double MA = sum * 1.0 / C, imb = 0;
		sort(mass, mass+2*C);
		for(int i = 0; i < C; i++){
			cout << " " << i << ":";
			imb += abs(mass[i] + mass[2*C-1-i] - MA);
			if(mass[i]) cout << " " << mass[i];
			if(mass[2*C-1-i]) cout << " " << mass[2*C-1-i];
			cout << endl;
		}
                delete [] mass;
		printf("IMBALANCE %.5lf\n\n", imb);
	}
	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