考试鄙视.ppt

考试鄙视 非考试鄙视者，乃鄙视考试也。
From：
White&Light
1
问题描述
whence?这个学期考了n次试，每一次都有一个在[0~20000]的整数分数。whence?本来的状态应该是每一次考试都比前一次多一分（除第一次），但由于他很不稳定，偏差可能很大。对于第i次考试，如果有第j次考试满足：1<=j<i<=n且以第j次考试分数作为基准，估计的第i次考试成绩比实际成绩低，就说第i次考试鄙视了第j次考试（估计分可以超过20000）。为了提高自信，whence?想知道他这个学期所有考试总共有多少次鄙视。
2
输入格式： 第一行n（1<n<=100000）
第二行为n次考试成绩。
输出格式： 一行，这个学期所有考试的总共鄙视次数。（总数可能很大，只需要输出它mod 12345
样例输入：
4
1 3 3 5
样例输出：
3
3
多好的一道题啊，让ac都错了……（修改后的数据）
4
解法参考
其实这道题就是逆序对的变种，变成正序对而已。最朴素的方法就是枚举，不过时间太长了。我们先看一下朴素做法。
for i:=1 to n do
read(a[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if (a[i]+j-i<a[j]) then m:=m+1;
if m=12345 then m:=0;
end;
很简洁，但如果稍加改动，就能形成标准的顺序对
a[i]-i<a[j]-j
就是将a[i]+j-i<a[j]
移项
这样，a[i]就可以表示为第i次开始得分减去序号，若a[i]<a[j]，那么第j次考试就鄙视了第i次考试。
5
之后，就是将求正序对的程序改为求正序对的程序就行了。
在这里可以复****一下逆序对（因为没找到关于正序对的……）的求法，即归并排序的应用。
6
假设当前求的是子数列A[low..high]的逆序数，记为d（low，high）。
分治：将子数列A[low..high]分成数的个数尽量相等的两个部分，A[low..mid]和A[mid+1，high]（mid=（low+high）div 2）。如果逆序对中的两个数分别取自子数列A[low..mid]和A[mid+1..high]的话，则该类逆序对的个数记入f（low，mid，high）。显然:
d(low,high)=d(low,mid)+d(mid+1,high)+f(low,mid,high)
7
合并：显然，计算f（low，mid，high）的快慢是算法时效的瓶颈，如果依然用两重循环来计算的话，其时效不会提高。
我们要求计算出d（low，high）后，数列A[low..high]已排序。这样一来，当求出d（low，mid）和d（mid+1，high）后，A[low，mid]和A[mid+1，high]已排序。
设指针i，j分别指向A[low，mid]和A[mid+1，high]中的某个数，且A[mid+1]，..，A[j-1]均小于A[i]，但A[j]>=A[i]，那么A[mid+1..high]中比A[i]小的数共有j-mid-1个，如下图，将j-mid-1计入f（low，mid，high）。
8
由于A[low..mid]和A[mid+1..high]已经排序，因此只要顺序移动i，j就能保持以上条件，这是合并时间复杂度为线性时间的根本原因。例如从上图到下图的状态只需要将i顺序移动一个位置，将j顺序移动一个位置。
这样的话，我们就能在短时间内将本题解出来
9
参考程序
var
n:longint;
a,b:array[1..100000]of longint;
i:longint;
ans:longint;
procedure sort(left,right:longint);
var
mid:longint;
q,w,e:longint;
begin
if (left<>right) then
begin
mid:=(left+right)div 2;
sort(left,mid);
sort(mid+1,right);
10