?? post.cpp
字號:
/* */
#include<fstream.h>
ifstream in("input.txt");
ofstream out("output.txt");
/* */
template <class T>
void BubbleSort(T a[], int n) //冒泡排序
{
for(int i=n; i>1; i--)
for(int j=0; j<i-1; j++)
if(a[j] > a[j+1])
Swap(a[j], a[j+1]);
}
/* */
template <class T>
void Swap(T &a, T &b)
{
T temp = a;
a = b;
b = temp;
}
/* */
template <class T>
int Partition(T a[], int p, int r, T x)
{
int i = p-1, j = r+1;
while(true)
{
while(a[++i]<x && i<=j); //空語句
while(a[--j]>x && j>=i); //空語句
if(i >= j) break;
Swap(a[i], a[j]);
}
return j;
}
/* */
template <class T>
T Select(T a[], int p, int r, int k) //最壞情況下的線性時間選擇算法
{
if(r - p < 75)
{
BubbleSort(&a[p], r-p+1);
return a[p+k-1];
}
else
{
for(int t=0; t<=(r-p-4)/5; t++)
{
int temp = 5*t;
BubbleSort(&a[p+temp], 5);
Swap(a[p+t], a[p+temp+2]);
}
T x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);
int i = Partition(a, p, r, x), j = i-p+1;
if(k <= j) return Select(a, p, i, k);
else return Select(a, i+1, r, k-j);
}
}
/* */
int main(void)
{
int i, num, mx, my, sl = 0;
in>>num;
int *Sx = new int[num];
int *Sy = new int[num];
for(i = 0; i < num; i++)
{
in>>Sx[i];
in>>Sy[i];
}
mx = Select(Sx, 0, num-1, (num+1)/2); //選擇X方向的坐標中位數
my = Select(Sy, 0, num-1, (num+1)/2); //選擇Y方向的坐標中位數
for(i = 0; i < num; i++)
{
if(mx >= Sx[i]) sl += mx - Sx[i];
else sl += Sx[i] - mx;
if(my >= Sy[i]) sl += my - Sy[i];
else sl += Sy[i] - my;
}
out<<sl;
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -