多关键字排序

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (500000)
int n;
struct score
{
	int no,a,b,c,d,e,f;
	friend bool operator<(const score a,const score b)
	{
		return (a.a!=b.a)?a.a>b.a:(a.b!=b.b)?a.b>b.b:(a.c!=b.c)?a.c>b.c:(a.d!=b.d)?a.d>b.d:(a.e!=b.e)?a.e>b.e:(a.f!=b.f)?a.f>b.f:a.no<b.no;
	}
}a[MAXN];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d%d%d%d%d%d",&a[i].no,&a[i].a,&a[i].b,&a[i].c,&a[i].d,&a[i].e,&a[i].f);
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++)
		printf("%d %d %d %d %d %d %dn",a[i].no,a[i].a,a[i].b,a[i].c,a[i].d,a[i].e,a[i].f);
	return 0;
}

翻转排序(sort)

题目描述

Alex得到了存放着一个1-n排列的容器。这个容器支持的唯一操作，是翻转排列的某一段。思考很久之后，他决定用以下方式让这个排列有序：

1 找到每一个极大的下降子序列（子序列要求连续）

2 对于每个长度大于1的极大下降子序列，对它进行翻转

3 如果排列依然不是有序的，转1

我们举一个例子：初始排列是(5 3 1 4 2)

一开始极大的下降子序列是(5 3 1)(4 2)

把这些序列翻转后得到1 3 5 2 4

接下来的极大下降子序列是(1)(3)(5 2)(4)

翻转后是13 2 5 4

接下来的极大下降子序列是(1)(3 2)(5 4)

翻转后是12 3 4 5，满足要求

定义翻转一个子序列的费用为1（注意一轮翻转的费用可能大于1），那么上面的费用一共是2+1+2=5。

现在，给你一个排列，你要求出对这个排列排序的费用。

另外题目保证：第一次划分时，所有极大下降子序列的长度都是偶数

输入

第一行一个整数N

第二行表示N个数的排列

输出

所需费用。如果不能排序，输出-1

样例输入

4

3 1 4 2

样例输出

3

数据范围

对于10%的数据，N<=10

对于40%的数据，N<=3000

对于100%的数据，N<=100000

可以证明一定能排序，否则一定能进行交换。

由于，第一次划分时，所有极大下降子序列的长度都是偶数，没有单个点，故之后的解尽可能在递增序列接口，长度不超过2

(6 5) (2 1) (4 3)

 5 (6--1 ) 2--3 4 

(7 6 1) 4 (5 3 2)

 1 6 (7 4 2) 3 5

并且第一轮翻转之后不会有长度>=3的极长下降子序列

于是问题变成了求逆序对的个数，归并排序或者树状数组解决

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define INF (0xfffffff)
int n,a[MAXN];
long long ans=0;
int le[MAXN],re[MAXN];
int len(int l,int r)
{
	return r-l+1;
}
void mergesort(int l,int r)
{
	if (l>=r) return;
	int m=(l+r)>>1;
	mergesort(l,m);
	mergesort(m+1,r);
	memcpy(le+1,a+l,sizeof(int)*(m-l+1));
	memcpy(re+1,a+m+1,sizeof(int)*(r-m));
	le[m-l+2]=re[r-m+1]=INF;
	int i=1,j=1;
	for (int k=l;k<=r;k++)
		if (le[i]<re[j])
		{
			a[k]=le[i];
			i++;
		}
		else
		{
			a[k]=re[j];
			j++;
			ans+=m-l+1-(i-1);
		}
}
int main()
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int h=1;
	for (int i=1;i<n;i++)
	{
		if (a[i]<a[i+1])
		{
			if (h!=i)
			{
				ans++;
				for (int j=1;j<=(i-h+1)/2;j++) swap(a[(i+h)/2-j+( (i-h)%2  ) ],a[(i+h)/2+j]);
//				for (int k=1;k<=n;k++) cout<<a[k]<<' ';
//				cout<<endl;
			}
			h=i+1;
		}
	}
	if (h!=n)
	{
		ans++;
		int i=n;
		for (int j=1;j<=(i-h+1)/2;j++) swap(a[(i+h)/2-j+( (i-h)%2  ) ],a[(i+h)/2+j]);
//		for (int k=1;k<=n;k++) cout<<a[k]<<' ';
//		cout<<endl;
	}

	mergesort(1,n);


	cout<<ans<<endl;
//	while (1);
	return 0;
}

求一组数的中位数

巨羡慕C党有sort用

Program P2388;
var
   n,i,j:longint;
   a:array[1..10010] of longint;
Procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=a[(l+r) shr 1];
   repeat
      while a[i]<m do inc(i);
      while a[j]>m do dec(j);
      if i<=j then
      begin
         p:=a[i];a[i]:=a[j];a[j]:=p;
         inc(i);dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);


end;
begin
   read(n);
   for i:=1 to n do read(a[i]);
   qsort(1,n);
   writeln(a[(1+n) shr 1]);
end.

水题 裸的求逆序对数

Program P2299;
const
   maxn=500100;
Var
   tt,i,j,k,n:longint;
   a,le,re:array[1..maxn] of longint;
   ans:int64;
procedure mergesort(l,r:longint);
var
   i,j,k,mid:longint;

begin
   if l=r then exit;
   mid:=(l+r) shr 1;
   mergesort(l,mid);
   mergesort(mid+1,r);
   for i:=l to mid do le[i-l+1]:=a[i];
   le[mid+2-l]:=maxlongint;
   for i:=mid+1 to r do re[i-mid]:=a[i];
   re[r+1-mid]:=maxlongint;
   i:=1;j:=1;
   for k:=l to r do
   begin
      if (le[i]<=re[j]) then
      begin
         a[k]:=le[i];
         inc(i);
      end
      else
      begin
         a[k]:=re[j];
         inc(j);
         ans:=mid-l+1-(i-1)+ans;
      end;
   end;
end;
Begin
   while not eof do
   begin
      read(n);
      if n=0 then break;
      for i:=1 to n do read(a[i]);
      ans:=0;
      mergesort(1,n);
      writeln(ans);

   end;
end.

题目大意：对乱序列相邻2数移动，使得用最小步数使其有序

解法：归并排序

定理：

一个乱序序列的逆序数 = 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数

Program P1804;
const
   maxn=1000;
Var
   tt,i,j,k,n,ans:longint;
   a,le,re:array[1..maxn] of longint;

procedure mergesort(l,r:longint);
var
   i,j,k,mid:longint;

begin
   if l=r then exit;
   mid:=(l+r) shr 1;
   mergesort(l,mid);
   mergesort(mid+1,r);
   for i:=l to mid do le[i-l+1]:=a[i];
   le[mid+2-l]:=maxlongint;
   for i:=mid+1 to r do re[i-mid]:=a[i];
   re[r+1-mid]:=maxlongint;
   i:=1;j:=1;
   for k:=l to r do
   begin
      if (le[i]<=re[j]) then
      begin
         a[k]:=le[i];
         inc(i);
      end
      else
      begin
         a[k]:=re[j];
         inc(j);
         inc(ans,mid-l+1-(i-1));
      end;
   end;
end;
Begin
   readln(tt);
   for k:=1 to tt do
   begin
      writeln('Scenario #',k,':');
      read(n);
      for i:=1 to n do read(a[i]);
      ans:=0;
      mergesort(1,n);
      writeln(ans);



      writeln;
   end;
end.

哪为朋友帮我看看多关键字排序哪儿错了……

Program P1018;
type
   product=record
           b,id:longint;
           p:longint;
           end;
var
   t,n,i,j,total,count,maxb,mintb,price:longint;
   visit:array[1..100] of longint;
   m:array[1..100] of longint;
   a:array[1..100000] of product;
   ans:double;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function min(a,b:longint):longint;
begin
   if a>b then exit(b) else exit(a);
end;

procedure qsort(l,r:longint);
var
   i,j:longint;
   m,p:product;
begin
   i:=l;
   j:=r;
   m:=a[(l+r) div 2];
   repeat
      while a[i].b<m.b do inc(i);
 //     while (a[i].p<m.p) and (a[i].b=m.b) do inc(i);
 //     while (a[i].id<m.id) and (a[i].b=m.b) and (a[i].p=m.p) do inc(i);

      while a[j].b>m.b do dec(j);
//      while (a[j].p>m.p) and (a[j].b=m.b) do dec(j);
//      while (a[j].id>m.id) and (a[j].b=m.b) and (a[j].p=m.p) do dec(j);
      if i<=j then
      begin
         p:=a[i];
         a[i]:=a[j];
         a[j]:=p;
         inc(i);dec(j);
      end;


   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
end;
begin
  { assign(input,'p1018.in');
   assign(output,'p1018.out');
   reset(input);
   rewrite(output);
  }read(t);

   while t>0 do
   begin
      total:=0;
      read(n);
      mintb:=maxlongint;
      for i:=1 to n do
      begin
         read(m[i]);
         maxb:=0;
         for j:=1 to m[i] do
         begin
            inc(total);
            a[total].id:=i;
            read(a[total].b,a[total].p);
            maxb:=max(a[total].b,maxb);
         end;
         mintb:=min(maxb,mintb);
      end;
      qsort(1,total);
      ans:=0;
      for i:=1 to total-n+1 do
      begin
         if a[i].b>mintb then break;
         count:=0;
         fillchar(visit,sizeof(visit),0);
         visit[a[i].id]:=a[i].p;
         for j:=i+1 to total do
         begin
            if a[j].b<a[i].b then write('x');
            if (visit[a[j].id]=0) then
            begin
               inc(count);
               visit[a[j].id]:=a[j].p;
            end;
            visit[a[j].id]:=min(visit[a[j].id],a[j].p);
         end;
         if count<n-1 then break;
         price:=0;
         for j:=1 to n do inc(price,visit[j]);
         if ans<(a[i].b/price) then ans:=a[i].b/price;
      end;
      writeln(ans:3:3);

      dec(t);
   end;
{
   close(input);
   close(output);    }
end.

求逆序对数，2关键字排序

Program P1007;
var
   n,m,i,j,k,l,p:longint;
   a:array[1..200] of string;
   s:string;
   b,num:array[1..200] of longint;
function h(s:string):longint;
var
   i,j,a,c,g,t:longint;
begin
   a:=0;
   c:=0;
   g:=0;
   t:=0;
   h:=0;
   for i:=length(s) downto 1 do
   begin
      if s[i]='A' then inc(a);
      if s[i]='C' then
      begin
         inc(c);
         inc(h,a);
      end;
      if s[i]='G' then
      begin
         inc(g);
         inc(h,a+c);
      end;
      if s[i]='T' then
      begin
         inc(t);
         inc(h,a+c+g);
      end;
   end;
end;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
   s2:string;
begin
   i:=l;
   j:=r;
   m:=b[(l+r) div 2];
   repeat
      while b[i]<m do inc(i);
      while b[j]>m do dec(j);
      if i<=j then
      begin
         p:=b[i];
         b[i]:=b[j];
         b[j]:=p;
         p:=num[i];
         num[i]:=num[j];
         num[j]:=p;
{         s2:=a[i];
         a[i]:=a[j];
         a[j]:=s2;
}        inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
end;
begin
   readln(n,m);
   for i:=1 to m do
   begin
      readln(a[i]);
      b[i]:=h(a[i]);
      num[i]:=i;
   end;
   qsort(1,m);
   i:=1;
   while (i<m) do
   begin
      if b[i]<b[i+1] then inc(i)
      else
      begin
         for j:=i+1 to m do if b[j]<>b[i] then break;
         if (b[i]<>b[m]) then dec(J);
         for k:=i to j-1 do
            for l:=k+1 to j do
               if num[k]>num[l] then
               begin
                  p:=num[k];
                  num[k]:=num[l];
                  num[l]:=p;
 {                 s:=a[k];
                  a[k]:=a[l];
                  a[l]:=s;
  }             end;
         i:=j+1;
      end;
   end;
   for i:=1 to m do writeln(a[num[i]]);
end.