pipe_count.cpp

来自「设计一个算法」· C++ 代码 · 共 42 行

#include<iostream>
#include<fstream>
#include<cmath>
int c[20001],a[10001],b[10001],n;
using namespace std;
void countingsort()
{
    int i;
    memset(c,0,sizeof(c));
    for(i=0;i<n;i++)c[a[i]]++;
    for(i=1;i<=20000;i++)c[i]+=c[i-1];
    for(i=n;i>0;i--){
        b[c[a[i-1]]-1]=a[i-1];
        c[a[i-1]]--;
    }
}
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"error\n";
        exit(1);
    }
    while(fin>>n){        
        int i,sum=0,temp;        
        for(i=0;i<n;i++){
            fin>>temp>>a[i];
            a[i]+=10000;            
        }
        countingsort();
        int mid=b[n/2];
        for(i=0;i<n;i++)
            sum+=abs(a[i]-mid);
	//	fout<<mid-10000<<endl;
        fout<<sum<<endl;
    }
    fout.close();
    fin.close();
    return 0;
}