贪心延伸之排序

做贪心的时候遇到排序，小小的补习一下：

如果每次都自己写个冒泡之类的O(n^2)排序，不但程序容易超时，而且浪费宝贵的比赛时间，还很有可能写错。STL里面有个sort函数，可以直接对数组排序，复杂度为n*log2(n)。使用这个函数，需要包含头文件。
这个函数可以传两个参数或三个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一地址。也就是说，排序的区间是[a,b)。简单来说，有一个数组int a[100]，要对从a[0]到a[99]的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序。对向量v排序也差不多sort(v.begin(),v.end());

    排序的数据类型不局限于整数，只要是定义了小于运算的类型都可以，比如字符串类string。
    如果是没有定义小于运算的数据类型，或者想改变排序的顺序，就要用到第三参数——比较函数。比较函数是一个自己定义的函数，返回值是bool型，它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列，可以先定义一个比较函数cmp
bool cmp(int a,int b)
{
    return a>b;
}
   排序的时候就写sort(a,a+100,cmp);

   假设自己定义了一个结构体node
struct node{
    int a;
    int b;
    double c;
}

有一个node类型的数组node arr[100]，想对它进行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b还相同，就按c降序排列。就可以写这样一个比较函数：
以下是代码片段：
bool cmp(node x,node y)
{
if(x.a!=y.a) return x.a

if(x.b!=y.b) return x.b>y.b;
return return x.c>y.c;
} 排序时写sort(arr,a+100,cmp);

我需要注意的是

1.头文件，不管那么多先打几个再说

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std; 这一行必须打的，std我经常忘记打。。

struct st
{
int x;
int y;
} q[10005]; 结构体，这一道题做完延伸的重点，不用结构体没法排序（反正我暂时的水平是没办法）这里的st和int double一样，是一种类型。

bool cmp(st a,st b) 这里的st和int double一样，是一种类型。
{
return a.y>b.y;
}这个是判断从大往小排，不用这个的话默认是从小往大排，还有如果排Y的话就是 .Y 如果排X就是 .X 这里的a , b都是形参

以上都是在main函数外面的，切记不要放在里面了。

for(i=1; i<=n; i++)
scanf("%d %d",&q[i].x,&q[i].y);
sort(q+1,q+n+1,cmp);

在这个输入然后排序，1到n就是q+1到q+n+1

原题：POJ 2437

Description

Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools.

Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely.

Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools.

Input

* Line 1: Two space-separated integers: N and L

* Lines 2..N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the start and end points of a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap.

Output

* Line 1: The miminum number of planks FJ needs to use.

Sample Input

Sample Output

5
这一道题样例数据是没有多大用处的，自己想了几个
3 4
1 3
5 7
8 10      --------3

3 4
1 3
4 6
7 9      ---------------2

4 1
1 2
3 4
4 5
5 6    ----------4
本来超时的因为用冒泡排序，其他排序太复杂（自己懒得记而已）容易敲错，以前也不知道STL里面有个sort函数，╮(╯▽╰)╭

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct st
{
int x;
int y;
} q[10005];
bool cmp(st a,st b)
{
return a.y>b.y;
}
main()
{
int i,n,m,g,t,sum;

while(scanf("%d %d",&n,&m)!=EOF)
{
sum=0;
scanf("%d %d",&q[i].x,&q[i].y);
sort(q+1,q+n+1,cmp);

t=q[1].y;
for(i=1; i<=n; i++)
{
if(t>q[i].x&&t<=q[i].y)
{
while(t>q[i].x)
{
t=t-m;
sum++;
}
}
else if(t<=q[i].x)
continue;
else if(t>q[i].y)
{
t=q[i].y;
while(t>q[i].x)
{
t=t-m;
sum++;
}
}
}
printf("%d ",sum);
}
}