作业1：
求逆序数（归并排序求逆序数）
//分治法：两个阶段，分和治，注意分和治的方法和边界条件
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//定义数组Aarray和数组Barray大小
public static int [] Aarray=new int[1000010];
public static int [] Barray=new int[1000010];
//记录逆序个数
public static long sum;
public static void merge(int a[],int begin,int end,int b[])
{
//边界条件，当分时只有一个元素时
if(begin==end)
{
return ;
}
//定义中间位置
int mid=(begin+end)/2;
//左递归
merge(a, begin, mid, b);
//右递归
merge(a, mid+1, end, b);
int i=begin,j=mid+1,pos=begin;
//合并左右两部分
while(i<=mid&&j<=end)
{
if(a[i]<=a[j])
{
b[pos++]=a[i++];
}
else {
b[pos++]=a[j++];
sum+=mid-i+1;//计算逆序数，如果a[i]比a[j]大的话，a[i]之后的值都比a[j]大，统计数目
}
}
//比较之后第一个排序段有元素剩余,把剩余的元素赋给b数组
while(i<=mid)b[pos++]=a[i++];
//比较之后第二个排序段有元素剩余,把剩余的元素赋给b数组
while(j<=end)b[pos++]=a[j++];
//将b中的元素赋值给a，以便下次比较使用
for(int k=begin;k<=end;k++)
{
a[k]=b[k];
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int tests=scanner.nextInt();//测试数据组数
while(tests--!=0)
{
int number=scanner.nextInt();//元素个数
//数组Aarray和数组Barray清零操作
Arrays.fill(Aarray, 0);
Arrays.fill(Barray, 0);
sum=0;
for(int i=0;i<number;i++)
{
Aarray[i]=scanner.nextInt();
}
//调用归并函数，用Barray数组当做中间数组，进行记录中间结果
merge(Aarray, 0, number-1, Barray);
System.out.println(sum);
}
}
}
作业2：
机器人登山问题
//贪心问题
//贪心策略：将所有机器人第i步到低i+1步排序，总是选择时间最短的，直到所走的路程等于山的长度
//时间复杂度：主要的时间复杂度主要集中在双重循环上，o(n2);空间复杂度，o(n)
import java.util.Arrays;
import java.util.Scanner;
public class Robot {
public static int record[]=new int[10000000];
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int tests=scanner.nextInt();//测试数据组数
while(tests--!=0)
{
int number,bigestStep,totalStep,answer=0,pos=0;
Arrays.fill(record, 0);//数组record清零
number=scanner.nextInt();//机器人的数目
bigestStep=scanner.nextInt();//机器人最多可以走的步数
totalStep=scanner.nextInt();//山总的长度
for(int i=0;i<number;i++)
{
//每个机器人都要登山，可以先把所有机器人的第一步都加上
int aNumber=scanner.nextInt();
answer+=aNumber;
for(int j=0;j<bigestStep-1;j++)
{
int bNumber=scanner.nextInt();
record[pos++]=bNumber-aNumber;//求每走一米所需要的时间，用record记录
aNumber=bNumber;
}
}
//将除了第一步以外的每走一米所需要的时间放到record数组中从小到大排序，然后以后剩下的步数从数组中依次读取，因为题目中描述的是连续攀登的路程越长，其攀登的速度就越慢
Arrays.sort(record,0,pos);
for(int k=0;k<totalStep-number;k++)
{
answer+=record[k];
}
System.out.println(answer);
}
}
}