【算法基础】贪心算法

博主： Fivk
发布时间：2021 年 05 月 04 日
1072 次浏览
1589字数
分类：算法基础

# 一、基本概念

所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

![](https://blog.fivk.cn/usr/uploads/2021/05/4270789413.png)

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

所以对采用的贪心策略一定要仔细分析其是否满足无后续性。

# 二、基本思路

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的局部最优解合成原来解问题的一个解

</div>

# 三、适用问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

</div>

# 四、实现框架

```C
从问题的某一初始解出发;
while(能朝给定总目标前进一步)
{
    利用可行的决策，求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;
```

# 五、贪心策略的选择

应为贪心算法只能通过解局部最优的策略来达到全局最优解，因此，一定要注意判断问题是否适应采用贪心算法策略，找到的解是否一定是问题的最优解。

# 六、经典案例

## 例1：排队打水问题

有n个人排队到r个水龙头去打水，他们装满水桶的时间为t1、t2、t3、t4……tn 为整数且个不相等，应如何安排他们的大水顺序才能是他们花费的时间最少（含等待时间）？

</div>

【输入样例】

```输入样例
4 2			//4人打水，2个水3龙头
2 6 4 5			//每个人的打水时间
```

【输出样例】

```输出样例
23				//总共花费时间
```

由于排队时，越靠前的计算次数越多，因此越小的排在越前面的出的结果越小（可以用数学方法简单证明，在这里就不再赘述），所以这道题可以用贪心算法解答，基本步骤为：

1. 将输入的时间按从小到大排序
2. 将排序后的时间依次放入每个水龙头的队列中
3. 统计，输出答案

* 程序1

```C
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>

using namespace std;

int main()
{
    int s[1000],a[1000],n,r; //a数组存放每个人的装水时间，b数组存放每个人的总时间（等待时间+打水时间） 
    memset(s,0,sizeof(s));  //数组初始化为0 
    memset(s,0,sizeof(a));
    scanf("%d%d",&n,&r);

int i,j=0,sum=0;
    for(i=1; i<=n; i++)
	    scanf("%d",&a[i]);
    sort(a+1,a+1+n); //STL 从小到大排序

for(i=1;i<=n;i++)
    {
        j++;
        if(j==r+1) j=1;    //前r个人为一组，r+1个人回到第一个水龙头
        s[j]+=a[i];        //加上等待时间
        sum+=s[j];
    }

printf("%d\n",sum);   //输出结果 
    system("pause");
    return 0;

}
```

* 程序2

```C
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;

int main()
{
    int a[1000],b[1000],n,r; //a数组存放每个人的装水时间，b数组存放每个人的总时间（等待时间+打水时间） 
    memset(a,0,sizeof(a));  //数组初始化为0 
    memset(b,0,sizeof(b));
    scanf("%d%d",&n,&r);

int i,sum=0;
    for(i=1; i<=n; i++)
	    scanf("%d",&a[i]);
    sort(a+1,a+1+n); //STL 从小到大排序

for(i=1;i<=r;i++)  //前r个人为一组，每个人的打水时间即为自己的装水时间。
	    b[i]=a[i];
    for(i=r+1;i<=n;i++)  //从第r+1个人开始，每个人的打水时间为等待时间+装水时间。 
	    b[i]=b[i-r]+a[i];
    for(i=1;i<=n;i++)    //累加每个人的打水时间
	    sum+=b[i];

printf("%d\n",sum);   //输出结果 
    system("pause");
    return 0;

}
```

两个都是差不多的

## 例2：均分纸牌(Noip2002)

有n堆纸牌，编号分别为1、2、3……、n。每堆有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为1的堆上取的纸牌，只能移动到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆纸牌数一样多。

例如 n=4时，这4堆纸牌数分别为：①9   ②8   ③17   ④6

移动3次可达到目的：

1. 从③取4张牌放到④：①9   ②8   ③13   ④10
2. 从③取3张牌放到②：①9   ②11   ③10   ④10
3. 从②取1张牌放到①：①10   ②10   ③10   ④10

> 【输入格式】
>
> n（n堆纸牌，1<=n<=100）
> a1 a2 a3 …… an （n堆纸牌，每堆纸牌初始数，1<=ai<=10000）

> 【输出格式】
>
> 所有堆均达到相等时最少移动次数。

</div>

【输入样例】

```输入样例
4
9 8 17 6
```

【输出格式】

```输出格式
3
```

如果你想把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10，原张数9，8，17，6变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的-1变为0，只需将-1张牌移到它的右边（第二堆）-2中，结果就是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需要将第3堆中的4移动到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问负数牌怎么移动，不违背题意吗？其实从第i堆移动-m张导i+1堆，等价于从的i+1堆移动到的i堆，步数是一样的。

如果张数中本来就有为0的，怎么办？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变成0了，可节省1步，余下继续。

* 基本框架

```c
cin>>n;
ave = 0;
step = 0;
for(i=1;i<=n;i++)
{
    cin>>a[i];
    ave+=a[i];  //读入各堆牌张数，求总张数ave
}
ave/=n;         //求牌的平均张数
for(i=1;i<=n;i++)
{
    a[i]-=ave;  //每张牌的张数减去平均数
}
i=1;
j=n;
while(a[i]==0&&i<n) i++;    //过滤左边的0
while(a[j]==0&&j>1) j--;    //过滤右边的0
while(i<j)
{
    a[i+1]+=a[i];           //将第i堆牌移到第i+1堆中去
    a[i]=0;                 //第i堆牌移走后变为0
    step++;                 //移牌步数计数
    i++;                    //对下一堆牌进行循环操作
    while(a[i]==0&&i<j)     //过滤移牌过程中产生的0
    {
        i++;
    }
    cout<<step<<endl;
}
```

* 参考程序

```C
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;

int main()
{
    int n,i,ave=0,count=0;
    cin>>n;
    int a[n];
    memset(a,0,sizeof(a));
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        ave+=a[i];
    }

ave/=n;

for(i=0;i<n;i++)
    {
        a[i]-=ave;
    }

for(i=0;i<n-1;i++)
    {
        if(a[i]!=0)
        {
            count++;
            while(a[i])
            {
                a[i+1]-=a[i];
                a[i]=0;
            }
        }
    }
    cout<<"count = "<<count<<endl;
    system("pause");
    return 0;
}
```

基本题，本题有3点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是要过滤掉0（不是所有的0，如-2，3，0，-1中的0是不能过滤的）；三是负数张牌也可以移动，这是关键总的关键。

## 例3：删数问题(Noi1994)

输入一个高精度的正数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。

输出新的正整数。（n不超过240位）

输入数据均不需判错。

> 【输入格式】
>
> n
>
> s

> 【输出格式】
>
> 13

</div>

【输入样例】

```输入样例
175438
4
```

【输出样例】

```输出样例
13
```

由于正整数n的有效位为240位，所以很自然的采用字符串类型存贮n。那么如何决定哪s位被删除呢？是不是最大的s位数呢？显然<span style="color:#8B0000">不是删除最大的s位数</span>，很容易举出一些反例。为了尽可能逼近目标，***我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到的位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除的一个递减区间的首字符，这样删一位，便成了一个新的数字字符串***。然后回到串首，按上述规则再删下一个数字。重复以上过程s次为止，剩下的数字串便是问题的解了。

![](https://blog.fivk.cn/usr/uploads/2021/05/1895543201.png)

这样，删数问题就与如何寻找递减区间首字符这样一个简单的问题对应起来。不过还要注意一个细节问题，就是可能会出现字符串首有若干个0的情况，甚至整个字符串都是0的情况。

```C
#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;

int main()
{
    int s,i,j,k,m,len;
    char n[241]="";
    cin>>n;
    cin>>s;
    len=strlen(n);
    for(i=0;i<s;i++)            //一共需要删除s个字符
    {
        for(j=0;j<len-1;j++)    //从串首开始找
        {
            if(n[j]>n[j+1])         //找到第一个符合条件的数
            {
                for(k=j;k<len-1;k++)    //删除(移动覆盖)字符串n的第j个字符，后面字符往前整
                {
                    n[k]=n[k+1];
                }
                break;  //一次只找第一个
            }
        }
        len--;      //删了一个，长度减一
        //如果是最后一位，len--，也会去掉最后一位，后面输出不到最后一位
    }
    j=0;
    m=len;
    while(n[j]=='0'&&m>1)
    {
        j++;
        m--;
    }

for(i=j;i<len;i++)
    {
        cout<<n[i];
    }
    cout<<endl;
    system("pause");
    return 0;
}
```

## 例4：拦截导弹问题(Noip1999)

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能达到任意高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度不大于3000的正整数）。计算要拦截所有导弹的最小配置需要配备多少套这种导弹拦截系统。

> 【输入格式】
>
> n颗依次飞来的高度(i<=n<=1000)

> 【输出格式】
>
> 要拦截所有导弹最小配备的系数k。

</div>

【输入格式】

```输入格式
389 207 155 300 299 170 158 65
```

【输出格式】

```输出格式
2
```

按照题意，被一套系统拦截的所有导弹中，最后一枚导弹的高度最低。

设：k为当前配置的系数数；

l[k]为被第k套系统拦截的最后一枚导弹的高度，简称系统k的最低高度(1<=k<=n)。

我们首先设导弹1被系统1所拦截(k ← 1, l[k] ← 导弹1的高度)。然后依次分析导弹2，……，导弹n的高度、

若导弹i的高度高于所有系统的最低高度，则判定导弹i不能被这些系统所拦截，应增加一套系统来拦截导弹i(k ← k + 1,l[k] ← 导弹i的高度)；若导弹i低于某些系统的最低高度，那么导弹i均可被这些系统所拦截。究竟选择哪个系统拦截可使得配备的系统数量最少，我们不得不采用贪心策略，选择其中最低高度最小(即导弹i的高度与系统最低高度最接近)的一套系统p(l[p]=min{l[j] | l[j]  > 导弹i的高度}；l[p] ← 导弹i的高度)(i<=j<=k)。这样可使的一套系统拦截的导弹数尽可能增多。

依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数。

* 基本框架

```c
k=1;
l[k]=导弹1的高度；
for(i=2;i<=n;i++)
{
    p=0;
    for(j=1;j<=k;j++)
    {
        if(l[j]>=导弹i的高度)
        {
            if(p==0)
            {
                p=j;
            }else if(l[j]<l[p]){
                p=j;        //贪心
            }
        }
    }
        if(p==0)
        {
            k++;            //增加一套新系统
            l[k]=导弹i的高度;
        }else{
            l[p]=导弹i的高度;   //贪心，更新第p套系统的最低高度
        }
}
输出应配备的最少系统数k。
```

* 参考程序

```C
#include<bits/stdc++.h>
using namespace std;

int n,i,k,x,p,j,a[1001],l[1001];

int main()
{
    freopen("missile.in","r",stdin);
    freopen("missile.out","w",stdout);
    while(scanf("%d",&x)==1) a[++n]=x;  //a[i..n]敌方导弹高度

k=1;            //至少需要k套拦截系统
    l[1]=a[1];      //第一套拦截系统的初始高度l[i]=第一枚敌方导弹的高度a[1]

for(i=2;i<=n;i++)   //依次考察敌方导弹a[2...n]的高度
    {
        p=0;            //用拦截系统l[p]去拦截敌方导弹a[i]
        for(j=1;j<=k;j++)       //现有拦截系统l[j=1...k]
        {
            if(l[j]>a[i])       //拦截系统l[j]可用
            {
                if(p==0)        //首次发现可拦截a[i]的系统l[j]
                {
                    p=j;        //记录拦截系统编号
                }else if(l[j]<l[p]) //l[j]是比l[p]更优的解
                {
                    p=j;        //更新拦截系统编号
                }
            }
        }

if(p==0)
        {
            l[++k]=a[i];    //产生一个新的拦截系统l[k+1]
        }else{
            l[p]=a[i];      //刷新现有拦截系统l[p]的高度=a[i]
        }
    }

cout<<k<<endl;
    fclose(stdin);
    fclose(stdout);
    system("pause");
    return 0;
}
```

## 例5：活动选择

在最近几天有n个活动，这些活动都有需要使用的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，办公室人员只好让一些活动放弃用礼堂而使用其他教师。

现在给出n个活动使用礼堂的起始时间 begini 和结束时间 endi (begini < endi)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。

> 【输入格式】
>
> 第1行一个整数n(n<=1000)
>
> 接下来n行，每行两个整数，第1个begini，第二个是endi (begini<endi<32767)

> 【输出格式】
>
> 输出最多能安排的活动个数

</div>

【输入样例】

```输入格式
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
```

【输出样例】

```输出样例
4
```

算法模型：给n个开区间(begini,endi)，选择尽量多的区间，使得两两不交。

做法：首先按照end1<=end2<=……<=endn的选择顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。

正确性：如果不选end1，假设第一个选择的是endi，则如果endi和end1不交叉则多选一个end1更划算；如果交叉则把endi换成end1不影响后续选择。

![](https://blog.fivk.cn/usr/uploads/2021/05/3703276452.png)

```C
#include<iostream>
using namespace std;

int n,begin[1001],end[1001];

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>begin[i]>>end[i];
    }
}

void qsort(int x,int y)
{
    int i,j,mid,t;
    i=x;
    j=y;
    mid=end[(x+y)/2];

while(i<=j)
    {
        while(end[i]<mid) i++;
        while(end[j]>mid) j--;
        if(i<=j)
        {
            t=end[j];
            end[j]=end[i];
            end[i]=t;
  
            t=begin[j];
            begin[j]=begin[i];
            begin[i]=t;
            i++;
            j--;
        }
    }
    if(x<j) qsort(x,j);
    if(i<y) qsort(i,y);
}

void solve()
{
    int ans=0;
    for(int i=1,t=-1;i<=n;i++)  //在初始化循环变量的同时，初始化t，
                                //令t=-1可以使第一个区间与其他区间操作相同
    if(begin[i]>=t)             //如果当前活动与之前最后结束的活动不冲突，就接受当前活动
    {
        ans++;
        t=end[i];				//如果当前活动与之前最后结束的活动不冲突，就接受当前后动 
    }
    cout<<ans<<endl;
}

int main()
{
    init();
    qsort(1,n);
    solve();
    return 0;
}
```

* 这是自己用结构体写的，sort排序

```cpp
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;

struct Time
{
	int begin;
	int end;
};

bool cmp(struct Time a, struct Time b)
{
    return a.end<b.end;
}

int main()
{
	int n,i,count=0,t=-1;
	cin>>n;
	Time date[n];

for(i=0;i<n;i++)
    {
        cin>>date[i].begin;
        cin>>date[i].end;
    }

sort(date,date+n,cmp);

for(i=0;i<n;i++)
    {
        if(date[i].begin>t)
        {
            count++;
            t=date[i].end;
        }
    }

cout<<"count = "<<count<<endl;
    system("pause");

return 0;
}
```

## 例6：整数区间

请编程完成1一下任务：

1. 从文件中读取闭区间个数以及他们的描述；
2. 找到一个含元素个数最少的集合使得对于每一个区间，都至少有一个整数属于该集合，输出该集合的袁术个数。

> 【输入格式】
>
> 首行包括区间的数目n，1<=n<=10000,接下来n行，每行包括两个整数a、b，被一个空格隔开，0<=a<=b<=10000,他们是某一个区间的开始值和结束值。

> 【输出格式】
>
> 第1行集合元素的个数，对于每一个区间都至少有一个整数属于该区间，且集合所包含元素数目最少。

</div>

算法模型：给n个闭区间[ai,bi]，在数轴上选尽量少的点，使每个区间内至少有一个点。

算法：首先按b1<=b2<=……<=bn排序。每次标记当前区间的右端点x，并右移动当前区间指针，直到当前区间不包含x，再重复上述操作。

如图，如果选择灰色点，移动到黑色点更优。

![](https://blog.fivk.cn/usr/uploads/2021/05/3708317839.png)

```C
#include<iostream>
using namespace std;

int a[10001],b[10001],sum=0,n,m;
void qsort(int x,int y)			//多关键字快排 
{
	int i,j,mid1,mid2,t;
	i=x;
	j=y;
	mid1=b[(x+y)/2];
	mid2=a[(x+y)/2];
	while(i<=j)
	{
		while(b[i]<mid1||((b[i]==mid1)&&(a[i]<mid2))) i++;
		while(b[j]>mid1||((b[j]==mid1)&&(a[j]>mid2))) j--;
		if(i<=j)
		{
			//交换b 
			t=b[j];
			b[j]=b[i];
			b[i]=t;

//交换a
			t=a[j];
			a[j]=a[i];
			a[i]=t; 
			i++;
			j--;
		}
	}

if(x<j) qsort(x,j);
	if(y>i) qsort(i,y);
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	qsort(1,n);
	for(int i=1,x=-1;i<=n;i++)		//在初始化循环变量的同时，初始化x 
	{								//令x=-1 可以使第一个区间与其他区间的操作相同 
		if(x>=a[i]) continue;		//如果当前区间包含标记点，就跳过 
		sum++;
		x=b[i];						//更新标记点 
	}

cout<<sum<<endl;

return 0;
}
```

最后修改：2021 年 09 月 12 日

如果觉得我的文章对你有用，请随意赞赏

【算法基础】贪心算法

Fivk • 2021 年 05 月 04 日

# 一、基本概念

![](https://blog.fivk.cn/usr/uploads/2021/05/4270789413.png)

所以对采用的贪心策略一定要仔细分析其是否满足无后续性。

# 二、基本思路

</div>

# 三、适用问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

</div>

# 四、实现框架

# 五、贪心策略的选择

# 六、经典案例

## 例1：排队打水问题

</div>

【输入样例】

```输入样例
4 2			//4人打水，2个水3龙头
2 6 4 5			//每个人的打水时间
```

【输出样例】

```输出样例
23				//总共花费时间
```

1. 将输入的时间按从小到大排序
2. 将排序后的时间依次放入每个水龙头的队列中
3. 统计，输出答案

* 程序1

```C
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>

using namespace std;

int i,j=0,sum=0;
    for(i=1; i<=n; i++)
	    scanf("%d",&a[i]);
    sort(a+1,a+1+n); //STL 从小到大排序

for(i=1;i<=n;i++)
    {
        j++;
        if(j==r+1) j=1;    //前r个人为一组，r+1个人回到第一个水龙头
        s[j]+=a[i];        //加上等待时间
        sum+=s[j];
    }

printf("%d\n",sum);   //输出结果 
    system("pause");
    return 0;

}
```

* 程序2

```C
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;

int i,sum=0;
    for(i=1; i<=n; i++)
	    scanf("%d",&a[i]);
    sort(a+1,a+1+n); //STL 从小到大排序

printf("%d\n",sum);   //输出结果 
    system("pause");
    return 0;

}
```

两个都是差不多的

## 例2：均分纸牌(Noip2002)

有n堆纸牌，编号分别为1、2、3……、n。每堆有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。

现在要求找出一种移动方法，用最少的移动次数使每堆纸牌数一样多。

例如 n=4时，这4堆纸牌数分别为：①9   ②8   ③17   ④6

移动3次可达到目的：

1. 从③取4张牌放到④：①9   ②8   ③13   ④10
2. 从③取3张牌放到②：①9   ②11   ③10   ④10
3. 从②取1张牌放到①：①10   ②10   ③10   ④10

> 【输入格式】
>
> n（n堆纸牌，1<=n<=100）
> a1 a2 a3 …… an （n堆纸牌，每堆纸牌初始数，1<=ai<=10000）

> 【输出格式】
>
> 所有堆均达到相等时最少移动次数。

</div>

【输入样例】

```输入样例
4
9 8 17 6
```

【输出格式】

```输出格式
3
```

* 基本框架

* 参考程序

```C
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;

int main()
{
    int n,i,ave=0,count=0;
    cin>>n;
    int a[n];
    memset(a,0,sizeof(a));
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        ave+=a[i];
    }

ave/=n;

for(i=0;i<n;i++)
    {
        a[i]-=ave;
    }

## 例3：删数问题(Noi1994)

输出新的正整数。（n不超过240位）

输入数据均不需判错。

> 【输入格式】
>
> n
>
> s

> 【输出格式】
>
> 13

</div>

【输入样例】

```输入样例
175438
4
```

【输出样例】

```输出样例
13
```

![](https://blog.fivk.cn/usr/uploads/2021/05/1895543201.png)

```C
#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;

for(i=j;i<len;i++)
    {
        cout<<n[i];
    }
    cout<<endl;
    system("pause");
    return 0;
}
```

## 例4：拦截导弹问题(Noip1999)

输入导弹依次飞来的高度（雷达给出的高度不大于3000的正整数）。计算要拦截所有导弹的最小配置需要配备多少套这种导弹拦截系统。

> 【输入格式】
>
> n颗依次飞来的高度(i<=n<=1000)

> 【输出格式】
>
> 要拦截所有导弹最小配备的系数k。

</div>

【输入格式】

```输入格式
389 207 155 300 299 170 158 65
```

【输出格式】

```输出格式
2
```

按照题意，被一套系统拦截的所有导弹中，最后一枚导弹的高度最低。

设：k为当前配置的系数数；

l[k]为被第k套系统拦截的最后一枚导弹的高度，简称系统k的最低高度(1<=k<=n)。

我们首先设导弹1被系统1所拦截(k ← 1, l[k] ← 导弹1的高度)。然后依次分析导弹2，……，导弹n的高度、

依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数。

* 基本框架

* 参考程序

```C
#include<bits/stdc++.h>
using namespace std;

int n,i,k,x,p,j,a[1001],l[1001];

int main()
{
    freopen("missile.in","r",stdin);
    freopen("missile.out","w",stdout);
    while(scanf("%d",&x)==1) a[++n]=x;  //a[i..n]敌方导弹高度

k=1;            //至少需要k套拦截系统
    l[1]=a[1];      //第一套拦截系统的初始高度l[i]=第一枚敌方导弹的高度a[1]

if(p==0)
        {
            l[++k]=a[i];    //产生一个新的拦截系统l[k+1]
        }else{
            l[p]=a[i];      //刷新现有拦截系统l[p]的高度=a[i]
        }
    }

cout<<k<<endl;
    fclose(stdin);
    fclose(stdout);
    system("pause");
    return 0;
}
```

## 例5：活动选择

现在给出n个活动使用礼堂的起始时间 begini 和结束时间 endi (begini < endi)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。

> 【输入格式】
>
> 第1行一个整数n(n<=1000)
>
> 接下来n行，每行两个整数，第1个begini，第二个是endi (begini<endi<32767)

> 【输出格式】
>
> 输出最多能安排的活动个数

</div>

【输入样例】

```输入格式
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
```

【输出样例】

```输出样例
4
```

算法模型：给n个开区间(begini,endi)，选择尽量多的区间，使得两两不交。

做法：首先按照end1<=end2<=……<=endn的选择顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。

正确性：如果不选end1，假设第一个选择的是endi，则如果endi和end1不交叉则多选一个end1更划算；如果交叉则把endi换成end1不影响后续选择。

![](https://blog.fivk.cn/usr/uploads/2021/05/3703276452.png)

```C
#include<iostream>
using namespace std;

int n,begin[1001],end[1001];

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>begin[i]>>end[i];
    }
}

void qsort(int x,int y)
{
    int i,j,mid,t;
    i=x;
    j=y;
    mid=end[(x+y)/2];

int main()
{
    init();
    qsort(1,n);
    solve();
    return 0;
}
```

* 这是自己用结构体写的，sort排序

```cpp
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;

struct Time
{
	int begin;
	int end;
};

bool cmp(struct Time a, struct Time b)
{
    return a.end<b.end;
}

int main()
{
	int n,i,count=0,t=-1;
	cin>>n;
	Time date[n];

for(i=0;i<n;i++)
    {
        cin>>date[i].begin;
        cin>>date[i].end;
    }

sort(date,date+n,cmp);

for(i=0;i<n;i++)
    {
        if(date[i].begin>t)
        {
            count++;
            t=date[i].end;
        }
    }

cout<<"count = "<<count<<endl;
    system("pause");

return 0;
}
```

## 例6：整数区间

请编程完成1一下任务：

> 【输出格式】
>
> 第1行集合元素的个数，对于每一个区间都至少有一个整数属于该区间，且集合所包含元素数目最少。

</div>

算法模型：给n个闭区间[ai,bi]，在数轴上选尽量少的点，使每个区间内至少有一个点。

算法：首先按b1<=b2<=……<=bn排序。每次标记当前区间的右端点x，并右移动当前区间指针，直到当前区间不包含x，再重复上述操作。

如图，如果选择灰色点，移动到黑色点更优。

![](https://blog.fivk.cn/usr/uploads/2021/05/3708317839.png)

```C
#include<iostream>
using namespace std;

//交换a
			t=a[j];
			a[j]=a[i];
			a[i]=t; 
			i++;
			j--;
		}
	}

if(x<j) qsort(x,j);
	if(y>i) qsort(i,y);
}

cout<<sum<<endl;

return 0;
}
```

【算法基础】贪心算法

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【Java】面向对象知识结构及案例

【Git】使用Git和GitHub进行团队协作和版本控制

【基础框架】SpringMVC入门（下）

【ACM】小爱玩拼图

【C】函数指针：函数名代表函数的入口地址

【算法基础】贪心算法