一、经典例题
例一：排队接水
题意：n个人到r个水龙头接水，装满水桶的时间分别是t1,t2,t3....
接水时间是整数且互不相等，怎样安排顺序使每个人等待的
时间和最小。
题解：排队越靠前计算次数越多，因此越小的排在前面。
交换一下看看
例二：均分纸牌
题意：n堆纸牌，每堆若干张，但纸牌总数为n的倍数，求最少
移动多少次每堆纸牌的张数一样。
题解：贪心模拟，先让第一个人纸牌达到平均数，只交换1、2两
人的纸牌，不用考虑第2人纸牌不够给第1人的情况，因为分牌的
实际情况是让牌数最多的那堆先移动，所以第2人纸牌是绝对够提
供的。然后让第二人纸牌达到平均数。
例三：删数问题
题意：输入一个高精度正整数n，求删掉s个数位后，组成的新数最小。
题解：每次删一个使剩下的数最小的数。删去一个数后剩下数的位数
就确定了，只需要让最高位最小。
例四：导弹拦截问题
题意：给出n个炮弹高度，用导弹拦截，每一种导弹
发射的高度不能超过之前发射的高度，问一种导弹最多拦截
多少，要拦截所有需要多少导弹。
题解：第一问最长下降子序列。第二问：
做法一：贪心让之前高度最小的导弹拦截。
做法二：最少链划分 = 最长反链长度
做法二就是求最长上升序列长度。
例五：活动选择
题意：选择尽量多的区间，两两不相交。
题解：按结束时间排序，每次选择区间右端点最小的，
为剩下的区间留下更多的空间。
例六：整数区间
题意：数轴上有ｎ个区间，选择尽量少的点使每个区间都有点
题解：通俗的想，把区间想成一块块木板，把要找的点想成钉子，
如果你的钉子很靠前的话，后面的木板就可能钉不到，每次把钉子
钉在你要钉的木板最后。
CODEVS线段覆盖大全//以前做的和现在码风不一样，一样好看=u=
PS:有的不是贪心一起整理了。
a、最多不相交线段覆盖所有区间
题解：右端点升序排序，左端点相同右端点小的优先。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct E
{
int x,y;
}s[];
bool cmp(E a,E b)
{
if(a.y==b.y)return a.x<b.x ;
return a.y<b.y;
}
int n,ans,last;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&s[i].x,&s[i].y);
if(s[i].x>s[i].y)
swap(s[i].x,s[i].y);
}
sort(s+,s+n+,cmp);
for(int i=;i<=n;i++)
if(s[i].x>=last)
{
ans++;
last=s[i].y;
}
printf("%d\n",ans);
return ;
}
线段覆盖1
b、n条线段，每条选段有价值，求选两两不相交的线段，并使得价值和最大。
题解：不是贪心，是动态规划了。
dp[i]表示第i条线段选的最大价值。转移从不相交的转移来就可以了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct E
{
int x,y,v;
}s[];
int n,ans,f[];
bool cmp(E a,E b)
{
return a.y<b.y;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].v);
sort(s+,s+n+,cmp);
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
if(s[i].x>=s[j].y)
f[i]=max(f[j]+s[i].v,f[i]);
for(int i=;i<=n;i++)
ans=max(ans,f[i]);
printf("%d\n",ans);
}
线段覆盖2
c、和线段覆盖1一样
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct E
{
int x,y;
}s[];
bool cmp(E a,E b)
{
if(a.y==b.y)return a.x<b.x ;
return a.y<b.y;
}
int n,ans,last;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&s[i].x,&s[i].y);
if(s[i].x>s[i].y)
swap(s[i].x,s[i].y);
}
sort(s+,s+n+,cmp);
for(int i=;i<=n;i++)
if(s[i].x>=last)
{
ans++;
last=s[i].y;
}
printf("%d\n",ans);
return ;
}
线段覆盖3
d、和线段覆盖2一样，只是范围变大。
排序后。f[i]表示前i个线段所得最大值，线段覆盖3是n^2,从前一个
不想交的线段转移来。优化就是前缀最大值+二分查找，找右端点
小于当前线段左端点的线段p，从前缀p的最大值转移。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct E
{
long long x,y,v;
}s[];
long long mx[],f[],ans;
bool cmp(E a,E b)
{
return a.y<b.y;
}
int n;
long long erf(int l,int r,int x)
{
while(l<=r)
{
long long mid=l+(r-l)/;
if(s[mid].y>x)r=mid-;
else l=mid+;
}
return r;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld%lld%lld",&s[i].x,&s[i].y,&s[i].v);
sort(s+,s+n+,cmp);
for(int i=;i<=n;i++)
{
f[i]=max(mx[erf(,i-,s[i].x)]+s[i].v,f[i]);
ans=max(ans,f[i]);
mx[i]=max(f[i],mx[i-]);
}
printf("%lld\n",ans);
return ;
}
线段覆盖4
e、和4相同。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct E
{
long long x,y,v;
}s[];
long long mx[],f[],ans;
bool cmp(E a,E b)
{
return a.y<b.y;
}
int n;
long long erf(int l,int r,int x)
{
while(l<=r)
{
long long mid=l+(r-l)/;
if(s[mid].y>x)r=mid-;
else l=mid+;
}
return r;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld%lld%lld",&s[i].x,&s[i].y,&s[i].v);
sort(s+,s+n+,cmp);
for(int i=;i<=n;i++)
{
f[i]=max(mx[erf(,i-,s[i].x)]+s[i].v,f[i]);
ans=max(ans,f[i]);
mx[i]=max(f[i],mx[i-]);
}
printf("%lld\n",ans);
return ;
}
线段覆盖5
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
以上是《信息学奥赛一本通》的例题，我的博客贪心分类里都有代码。
很多贪心题目，都会依靠经典题的思想或者是变形。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
二、历年NOIP贪心题目
题目一、Noip2011观光公交
题意：n个景点和游客上下车时间，有k个加速器可以使边长-1，
如何使用加速器使乘客旅行时间总和最小。
题解：一开始我只是在经过人数最多的边加加速器，后来发现
在i边使用加速器后会影响后面的人，很好的题。
题目二：Noip2012国王游戏
题意：n个人，每个人左右手都有数字，每个人获得的值是前面人左
手乘积除以本人右手乘积。
题解：交换两个大臣的位置比较交换后的差别
题目二：Noip2012疫情控制
题意：略。
题解：本来看起来是个很难的图论题，贪心是解决问题的突破口。
所有士兵向上走覆盖的子树多。
题目三、Noip2013火柴排队
题意：求sigma(ai-bi)^2最小
题解：要想sigma(ai-bi)^2最小，需要ai与bi的差最小，将ai,bi排序，
小的对应小的，大的对应大的。
三、总结
贪心的策略：
（1）证明，常用的方法是交换。
（2）猜呗。
贪心的思想：只顾眼前，忽略整体，只看局部。
CCL贪心大法好！