?? soldier.cpp
字號:
#include<stdlib.h>
#include <fstream.h>
#include <math.h>
#define size 10000
template<class T>
T RandomizedSelect(T a[],int p,int r,int k)
{
if(p==r) return a[p];
int i=RandomizedPartition(a,p,r),j=i-p+1;
if(j==2&&a[p]==a[r]) return a[p];
if(k<=j) return RandomizedSelect(a,p,i,k);
else return RandomizedSelect(a,i+1,r,k-j);
}
template<class T>
int RandomizedPartition(T a[],int p,int r)
{
int i=Random(p,r);
Swap(a[i],a[p]);
return Partition(a,p,r);
}
template<class T>
int Partition(T a[],int p,int r)
{
int i=p,j=r+1;
T x=a[p];
while(true)
{
while(a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
template<class T>
void RandomizedQuickSort(T a[],int p,int r)
{
if(p<r)
{
int q=RandomizedPartition(a,p,r);
RandomizedQuickSort(a,p,q-1);
RandomizedQuickSort(a,q+1,r);
}
}
inline int Random(int p,int r)
{
return p+rand()%(r-p+1);
}
template<class T>
inline void Swap(T& a,T& b)
{
T temp=a;
a=b;
b=temp;
}
int Xstep(int x[],int n)
{
int step=0;
int m=(n+1)/2;
RandomizedQuickSort(x,0,n-1);
for(int i=0;i<n;i++)
x[i]=x[i]-i;
int mid=RandomizedSelect(x,0,n-1,m);
for(i=0;i<n;i++)
step+=abs(x[i]-mid);
return step;
}
int Ystep(int y[],int ymax,int ymin)
{
int step=0;
while(ymax>ymin)
{
if(y[ymax]==y[ymin])
{
step+=y[ymax]*(ymax-ymin);
ymax--;
ymin++;
}
else if(y[ymax]>y[ymin])
{
step+=y[ymin]*(ymax-ymin);
y[ymax]=y[ymax]-y[ymin];
ymin++;
}
else
{
step+=y[ymax]*(ymax-ymin);
y[ymin]=y[ymin]-y[ymax];
ymax--;
}
}
return step;
}
int main()
{
ifstream ins("input.txt");
ofstream outs("output.txt");
int y[20001]={0};
int a,b,c,e,n,ymax,ymin;
ins>>n;
int *x=new int[n];
for(int i=0;i<n;i++)
{
ins>>x[i];
ins>>e;
if(i==0){ymax=e;ymin=e;}
y[e+size]++;
if(e>ymax) ymax=e;
if(e<ymin) ymin=e;
}
a=Xstep(x,n);
b=Ystep(y,ymax+size,ymin+size);
delete []x;
c=a+b;
cout<<a<<endl;
cout<<b<<endl;
outs<<c;
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -