| ||||||||||
| 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 | |||||||||
一道好题被数据规模毁了。。。O(nlogn)可做思路很简单,就是排序之后补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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator