前述
首先介绍一下有关C++里面排序的模板, 包含的头文件是1
#include<algorithm>
常用的几种用法:
sort函数
1) 比如int x[N], 有n个元素, 直接使用sort(x,x+n);
2) 定义比较模式cmp, 然后使用sort(x,x+n,cmp);
比如(按下面的方法使用):1
2
3
4
5
6
7
8
9
10
11
12
13
14#include <algorithm>
struct pix{
int x,y;
}p[1000+5];
int cmp(const pix &a, const pix &b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
sort(p,p+n,cmp);
qsort函数
也需要定义比较模式, 并且可以按照下面所示方法使用1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#include <algorithm>
struct Node{
int x,y;
};
int cmp(const void* a, const void* b)
{
Node* m = (Node *)a;
Node* n = (Node *)b;
if (m->x==n->x)
return m->y - n->y;
return m->x-n->x;
}
qsort(mid,m,sizeof(mid[0]),cmp);
现在言归正传, 讲几道有关排序的POJ
POJ1723
问题描述:给你一些士兵的坐标，使用尽量少的步数将士兵移到某一横排，并且每个士兵的位置唯一。
思路就是先按照y的坐标进行排序，将所有的士兵先移动到y的中位数对应的横排，现在遇到的一个问题就是可能多个士兵占用同一个x，怎么处理？我们的目标是将这些占用同一个x的士兵用尽量少的步数展开。首先想到的是假设有个起点a，这些士兵刚好排列在a+i上，如果没有怎么办？显然应该是abs(a+i-xi)的最小值，这里有个问题xi应该首先排好序否则a+i-xi不对应或者偏离很远。abs(a+i-xi)的最小值也即是abs(a-(xi-i))的最小值，于是a就是xi-i的中位数。
比如：x1=x2=x3=2，xi-i=1, 0, -1, 那么中位数a=0, 最小值2。
源代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#include <iostream>
#include <algorithm>
using namespace std;
#define N 10000+5
int main()
{
int n,x[N],y[N];
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
sort(y,y+n);
sort(x,x+n);
for (int i=0;i<n;i++)
x[i] -= i;
sort(x,x+n);
int cntx = (n%2)?x[(n-1)/2]:(x[n/2]+x[n/2-1])/2;
int cnty = (n%2)?y[(n-1)/2]:(y[n/2]+y[n/2-1])/2;
int sum=0;
for (int i=0;i<n;i++)
sum +=(abs(cntx-x[i])+abs(cnty-y[i]));
printf("%d\n",sum);
return 0;
}
POJ2376
问题描述：给你N个时间段和一个时间T，求最少的时间段覆盖时间[1,T]，如果不能覆盖则输出结果-1。
解题思路：
1）根据所有时间段的起始点从小到大排序，如果起始点相等就根据结束点从小到大排序。
2）如果起始点不等于1显然覆盖不了，直接输出－1，否则循环过滤掉前面多个1。
3）使用贪心的策略来求解最小的段数。操作就是用end来保存每次符合要求的最大结束点top，此时计数＋1，如果某次的top<=end表明已经难以继续增加，直接退出比较是否比T大，如果比T大则输出计数值，否则输出－1。
源代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#define N 25000+5
struct INTER{
int start;
int end;
};
INTER p[N];
int cmp(const void* a, const void* b)
{
INTER *m = (INTER *)a;
INTER *n = (INTER *)b;
if (m->start == n->start)
return m->end - n->end;
return m->start - n->start;
}
int main()
{
int n,T;
while (scanf("%d%d",&n,&T)==2)
{
int i;
for (i=0;i<n;i++)
scanf("%d%d",&p[i].start,&p[i].end);
qsort(p,n,sizeof(p[0]),cmp);
if (p[0].start!=1){
printf("-1\n");
return 0;
}
i=0;
while (p[i].start==1 && i<n)
i++;
int cnt = 1;
int end = p[i-1].end;
int top = p[i-1].end;
while(i<n){
int cur = i;
while (p[i].start <= end + 1 && i < n)
{
top = max(top,p[i].end);
i++;
}
if (cur==i || top<= end)
break;
cnt++;
end = top;
}
if (top >= T)
printf("%d\n",cnt);
else
printf("-1\n");
}
return 0;
}
POJ1971
问题描述：给你n个点的坐标，要求你找出平行四边形的个数。
解题分析：平行四边形有一个显著的特点就是对角线相交于某一点，而该点也是每条对角线的中点，那么比方说有k个点相交于某点，那么就应该有C(k,2)个平行四边形，这里的思路就是将所有坐标与其他点的坐标取平均值等到所有的中点，然后排序所有中点，进而容易查找在某中点的个数k，然后将所有的C(k,2)求和即得到平行四边形的个数。
源代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include <iostream>
#include <algorithm>
using namespace std;
struct Node{
int x,y;
}in[1005],mid[500005];
int cmp(const void* a, const void* b)
{
Node* m = (Node *)a;
Node* n = (Node *)b;
if (m->x==n->x)
return m->y - n->y;
return m->x-n->x;
}
int main()
{
int t,n,m;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d%d",&in[i].x,&in[i].y);
m=0;
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
{
mid[m].x = in[i].x+in[j].x;
mid[m++].y = in[i].y+in[j].y;
}
qsort(mid,m,sizeof(mid[0]),cmp);
int dk=1,sum=0;
for (int i=0;i<m;i++)
{
if (mid[i].x==mid[i+1].x && mid[i].y==mid[i+1].y && i!=m-1)
dk++;
else{
if (dk>1)
sum += (dk*(dk-1)/2);
dk = 1;
}
}
printf("%d\n",sum);
}
return 0;
}
POJ1788
题目描述：给你p个点的坐标，要求最小围住这p个点的篱笆长度。
解题分析：要求最小的篱笆长度，那么点应该在篱笆的拐角处，这样意味什么？比如你想计算y方向的篱笆长度，你需要先对x排序，如果x相等按y排序，这里有个点需要想到，就是对应每一个x，会有成对的y出现，这样才能求出y方向的篱笆长度，同理计算x方向的篱笆长度。两向篱笆长度想加即得到最小的篱笆长度。
源代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include <iostream>
using namespace std;
struct Node{
int x,y;
};
Node pix[100000+5];
int cmpx(const void *a, const void *b)
{
Node* m = (Node *)a;
Node* n = (Node *)b;
if (m->x == n->x)
return m->y - n->y;
return m->x - n->x;
}
int cmpy(const void *a, const void *b)
{
Node* m = (Node *)a;
Node* n = (Node *)b;
if (m->y == n->y)
return m->x - n->x;
return m->y - n->y;
}
int main()
{
int p,sum;
while(scanf("%d",&p)==1&&p!=0){
for (int i=0;i<p;i++)
scanf("%d%d",&pix[i].x,&pix[i].y);
sum=0;
qsort(pix,p,sizeof(pix[0]),cmpx);
for (int i=0;i<p;i=i+2)
sum += (pix[i+1].y-pix[i].y);
qsort(pix,p,sizeof(pix[0]),cmpy);
for (int i=0;i<p;i=i+2)
sum += (pix[i+1].x-pix[i].x);
printf("The length of the fence will be %d units.\n",sum);
}
return 0;
}