士兵战列.cpp.txt

在一个划分成网格的操场上

/*==========================
姓名：魏丽芬
学号：070321141
=========================*/
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

int k = 0;    //士兵数
int step = 0; //移动步数

bool order(int data[]);                     //插入排序
void quickSort(int data[], int p, int r);   //快速排序
int  part(int data[], int first, int last); //划分函数
void swap(int& m, int& n);                  //交换函数
int  forX(int data[]);                      //计算X轴方向上的移动步数
int  forY(int data[]);                      //计算Y轴方向上的移动步数

int main()
{
   ifstream fin("input.txt");
   ofstream fout("output.txt");

   fin>>k; //读取士兵数
   int* X=new int[k];
   int* Y=new int[k];
   for(int i=0; i<k; i++)
   {
      fin>>X[i]>>Y[i]; //读取士兵的x、y坐标
   }

   //计算最优移动步数
   quickSort(X, 0, k-1); //x轴方向 快速排序
   quickSort(Y, 0, k-1); //y轴方向 快速排序
   step += forY(Y);
   step += forX(X);
   fout<<step; //输出移动的步数
   //释放内存
   delete [] X;
   delete [] Y;
   return 0;
}

/*插入排序的函数(升序)*/
bool order(int data[])
{
   for(int i=1; i<k; i++)
   {
      for(int j=i-1; j>=0; j--)
      {
         if(data[j] > data[j+1]) //若前个数据比后一个大
            swap(data[j], data[j+1]); //交换这两个数据
         else
            break;
      }
   }
   return true;
}

/*计算Y轴方向上的移动步数*/
int forY(int data[])
{
   int count=0;
   for(int n=0; n<k; n++)
   {
      count += abs(data[n]-data[k/2]);
   }
   return count;
}

/*计算X轴方向上的移动步数*/
int forX(int data[])
{
   /*============================================================================
   设,共n个士兵,他们相应的X轴坐标为：X0, X1, X2, ……, Xn-1
   设,士兵需要移动到的“最终位置”的X轴坐标值为：leftKey, leftKey+1, leftKey+2 …… leftKey+(n-1)
   则所求最优步数count=|X0-leftKey| + |X1-(leftKey+1)| + |X2-(leftKey+2)| + …… + |Xn-1-(leftKey+(n-1))|
   经过变形count=|X0-leftKey| + |(X1-1)-leftKey| + |(X2-2)-leftKey| + …… + |(Xn-1-(n-1))-leftKey|
   ============================================================================*/
   int count = 0;
   for(int i=0; i<k; i++)
   {
      data[i] -= i;
   }
   //然后再进行快速排序
   quickSort(data, 0, k-1);
   int leftKey = data[k/2];
   if(leftKey < -10000)
     leftKey = -10000;    //X0士兵 x轴坐标的下限
   else if(leftKey+k-1 > 10000)
     leftKey = 10000-k+1; //X0士兵 x轴坐标的上限

   for(int m=0; m<k; m++)
   {
      count += abs(data[m]-leftKey); //统计X轴方向上的移动步数
   }
   return count;
}

/*两数交换的函数*/
void swap(int& m, int& n)
{
   int temp = m;
   m = n;
   n = temp;
}

/*快速排序的函数*/
void quickSort(int data[], int first, int last)
{
   if(first < last)
   {
      int mid = part(data, first, last);
      quickSort(data, first, mid-1); // 递归 对左子序列作划分
      quickSort(data, mid+1, last);  // 递归 对右子序列作划分
   }
}

/*划分函数*/
int part(int data[], int first, int last)
{
    srand(last-first+1); //初始化随机数发生器
    int ran = first+(last-first)*rand()/RAND_MAX;
    swap(data[first], data[ran]);
    int  i    = first;
    int  j    = last+1;
    int  key  = data[first];
    bool flag = true;

    while(flag)
    {
       while(data[++i] < key);
       while(data[--j] > key);
       if(i >= j)
         flag = false;
       else
         swap(data[i], data[j]);
    }
    data[first] = data[j];
    data[j] = key;
    return j;
}