UVA 10905(Children's Game-C的qsort函数和sprintf)

4th IIUC Inter-University Programming
Contest, 2005

A

Children’s Game

Input: standard input
Output: standard output

Problemsetter: Md. Kamruzzaman

给你 N 个正数. 如 123, 124, 56, 90 ,它们可以拼成 1231245690, 1241235690, 5612312490, 9012312456, 9056124123 etc. 有 24 种拼法, 9056124123 最大.

请你找出这个最大的数。

Input

每组数据第一行为 N (≤ 50). 接下来1行有 N 个正数,数据以  0 结尾.

Output

对每组数据,输出最大的拼法.

Sample Input

Output for Sample Input

4
123 124 56 90
5
123 124 56 90 9
5
9 9 9 9 9
0

9056124123
99056124123
99999


按照字符串连起来后(len相等)的字符串比较

值得一提的是qsort中cmp的写法(char[]无法用sort排序)

以及sprintf(占位符随便改,可以将任意类型转换成字符串)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (100+10)
int cmp(const void *a1,const void *b1)
{
	char *a=(char*)a1,*b=(char*)b1;
	char _a[MAXN*2]={0},_b[MAXN*2]={0};
	sprintf(_a,"%s%s",a,b);
	sprintf(_b,"%s%s",b,a);
	return strcmp(_b,_a);
}
int n;
char a[MAXN][MAXN];
int main()
{
	while(scanf("%d",&n)&&n)
	{
		for (int i=1;i<=n;i++) scanf("%s",a[i]);
		qsort(a+1,n,sizeof(a[1]),cmp);
		for (int i=1;i<=n;i++) printf("%s",a[i]);
		printf("n");
	}
	return 0;
}

Tyvj Q1027(多关键字排序)

多关键字排序

#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;
}

Tyvj P2058(Map)

c++ <map>的使用

其实由于x和y不相等,可以桶排的……

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<map>
using namespace std;
#define MAXN (1000+10)
#define MAXM (1000+10)
struct node
{
	int x,y,w;
	node():x(0),y(0),w(1){}
	node(int _x,int _y,int _w):x(_x),y(_y),w(_w){}

	friend bool operator<(const node a,const node b){ return (a.w!=b.w)?a.w<b.w:a.x+a.y>b.x+b.y;	}
	friend bool operator==(const node a,const node b){ return (a.x==b.x)&&(a.y==b.y);}
}a[MAXN];

int /*hash[MAXN+MAXM][2],*/n,m;
map<node,int> b;
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		a[i].w=1;
		for (int j=1;j<i;j++)
		{
			if (a[i]==a[j]) a[i].w++;
		}
	}
	sort(a+1,a+1+n);
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		b[node(x,y,0)]=1;
	}
	for (int i=n;i>=1;i--)
	{
		if (b.find(node(a[i].x,a[i].y,0))==b.end() )
		{
			cout<<a[i].x<<' '<<a[i].y<<endl;
			return 0;


		}
	}




	return 0;
}

翻转排序 (sort)

翻转排序(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;
}

POJ 2388(中位数)

求一组数的中位数

巨羡慕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.

POJ 2299(逆序对数)

水题 裸的求逆序对数

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.

POJ 1804(最小相邻数移动)

题目大意:对乱序列相邻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.

POJ 1018(多关键字排序还在wa…)

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

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.

POJ 1007(求逆序对数)

求逆序对数,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.