Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: