目录
声明：
本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的部分重要知识点、例题答案及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成 ，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》— 作者李煜东，强烈安利，好书不火系列，谢谢配合。
下方链接为学习笔记目录链接（中转站）
贪心
贪心是一种在每一次决策时都采用当前意义下最优策略的算法，因此，使用贪心算法要求问题的整体最优性可以由局部最优性导出。
贪心算法的正确性需要证明，常见的证明手段有：
- 微扰（邻项交换） 证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差，经常用于以排序为贪心策略的证明。
- 范围缩放 证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。
- 决策包容性
证明在任意局面下，做出局部最优策略以后，在问题状态空间中的可达到集合包含了做出其他任何决策之后的可到达集合。换言之，这个局部最优解提供的可能性包含其他所有策略提供的可能性。 - 反证法
- 数学归纳法
0. USACO07NOV Sunscreen
洛谷题目链接 ：https://www.luogu.com.cn/problem/P2887
其实本题可以看成区间覆盖问题，即求线段最多覆盖多少点，线段按右端点排序，防晒霜按防护值排序，只不过这里的线段有数量而已。
%%%yxc大佬，看完他的题解学到了一些实用的map的操作。
戳我看题解
整理了一下map 的操作：我是博客链接
yxc大佬的证明太强了，其实就是如果按照min排序，那么对于每一个防晒霜来说，不低于当前的牛的min，就一定不低于下一头牛的min，对于当前牛可用的两种防晒霜x和y来说，如果 spf[x]<spf[y]那么对于后面的牛来说，只能出现“x，y都能用”，“x，y都不能用”，和“x能用y不能用”这三种情况，因此这时选择用掉最大的是最优的。定好了一个边界以后，每次对于当前的牛，直接利用map中的upper_bound直接找到第一个大于max的防晒霜，并–找到第一个小于等于当前牛max的防晒霜，用掉。如果这种的防晒霜用完了，就从map 里erase掉。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const ll N=2507;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
int n,m;
pair<int,int>cow[N];
int main()
{
cin>>n>>m;
map<int,int>spfs;
over(i,1,n)scanf("%d%d",&cow[i].first,&cow[i].second);
over(i,1,m){
int spf,cover;
scanf("%d%d",&spf,&cover);
spfs[spf]+=cover;
}
sort(cow+1,cow+1+n);
int res=0;
spfs[0]=spfs[1001]=n;
for(int i=n;i>=1;--i){
auto spf=spfs.upper_bound(cow[i].second);
spf--;//这里的spf是map<>spfs的一个iterator,第一个大于cow[i].max的防晒霜
//--之后就是最后一个小于等于cow[i].max的防晒霜了
if(spf->first>=cow[i].first){
res++;
if(--spf->second==0)
spfs.erase(spf);
}
}
printf("%d\n",res);
return 0;
}
1.USACO06FEB Stall Reservations （贪心）
题目链接：https://www.luogu.com.cn/problem/P2859
输入样例：
5
1 10
2 4
3 6
5 8
4 7
输出样例：
4
1
2
3
2
4
思路不会了看这里：
https://www.acwing.com/solution/AcWing/content/1060/
贪心的思路还是很好想很基础的，但是这道题代码写起来脑壳痛，其中的细节颇多，特别是这个queue里的bug找的我头疼，遂写成博客以警惕自己
你见过哪些意想不到的bug ？（常见代码使用误区，下次一定还犯）
这道题剩下的也没什么，就是要注意输出每头牛的组的时候要+1，因为这里是从0开始的
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const int N=50010;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
#define a cows
#define q heap
#define ans id
int ans[N];
pair<PII, int>a[N];
int n,m;
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ ){
cin>>a[i].first.first>>a[i].first.second;
a[i].second=i;
}
sort(a,a+n);
priority_queue<PII,vector<PII>,greater<PII>>q;
//ans[1]=1;
//q.push(make_pair(a[1].first.second,1));
for (int i = 0; i < n; i ++ ){
if(q.empty()||q.top().first>=a[i].first.first){//！！！！！！
PII stall={a[i].first.second,q.size()};
ans[a[i].second]=stall.second;
q.push(stall);
}
else {
auto stall=q.top();
q.pop();
stall.first=a[i].first.second;
ans[a[i].second]=stall.second;
q.push(stall);
}
}
cout<<q.size()<<endl;
for (int i = 0; i < n; i ++ ){
cout<<ans[i]+1<<endl;
}
return 0;
}
2.UVA1193 Radar Installation（AcWing112. 雷达设备 ）
https://www.acwing.com/problem/content/114/
输入样例：
3 2
1 2
-3 1
2 1
输出样例：
2
对于x轴上的每个小岛，可以利用勾股定理计算出x轴上一段能够管辖它的区间 l[i] r[i]。问题转化为：给定N个区间，在x轴上放置最少的点，使每个区间至少包含一个点。
然后就是贪心操作了，将每个区间按照左端点 l[i]从小到大排序，用一个变量来维护已经安放的最后一个监控设备的坐标 pos，开始时 pos为负无穷。
首先对于每个区间 l[i] r[i]，有两种选择：
1.使用已有的监控设备管辖它
2.建造一台新的设备管辖它
我们的贪心策略是，可以选择1的时候不会选择2
依次考虑每个区间。如果当前区间i的左端点l[i]大于最后一台监控设备的坐标pos，则新增一台监控设备，并令 pos=r[i] （监控尽量向右放），否则就让最后一台已经安放的监控设备来管辖当前区间，并令 pos=min(r[i],pos)。
至于代码中的l和r直接用pair就好
AcWing112. 雷达设备的答案：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef pair<double,double> PDD;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const int N=50010;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
int n,m,d;
PDD a[N];
int x,y;
int main()
{
cin>>n>>d;
bool flag=false;
over(i,1,n){
scanf("%d%d",&x,&y);
if(y>d){
flag=true;
continue;
}
a[i].first=x-sqrt(d*d-y*y);
a[i].second=x+sqrt(d*d-y*y);
}
if(flag){
puts("-1");
return 0;
}
sort(a+1,a+1+n);
int res=0;
double pos=-23333333.1;
over(i,1,n){
if(a[i].first>pos){
res++;
pos=a[i].second;
}
else pos=min(pos,a[i].second);
}
printf("%d\n",res);
return 0;
}
UVA1193 Radar Installation的答案：（UVA的毒瘤输入输出 ）
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef pair<double,double> PDD;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const int N=50010;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
int n,m,d;
PDD a[N];
int x,y;
int main()
{
int t=0;
while(scanf("%d%d",&n,&d))
{
if(n==0&&d==0)break;
t++;
bool flag=false;
over(i,1,n){
scanf("%d%d",&x,&y);
if(y>d){
flag=true;
continue;
}
a[i].first=x-sqrt(d*d-y*y);
a[i].second=x+sqrt(d*d-y*y);
}
if(flag||d<0){//甚至还需要特判的d<0
printf("Case %d: -1\n",t);
continue;
}
sort(a+1,a+1+n);
int res=0;
double pos=-23333333.1;
over(i,1,n){
if(a[i].first>pos){
res++;
pos=a[i].second;
}
else pos=min(pos,a[i].second);
}
printf("Case %d: %d\n",t,res);
}
return 0;
}
3.P1080 国王游戏（高精+贪心）
按照每一个大臣左右手上数字的乘积升序排序，就是最优方案
这里需要用高精度操作，好~~长~~啊~~
#include <bits/stdc++.h>
using namespace std;
int now[20010],sum[20010],ans[20010],add[20010];
struct Node {
int a;
int b;
long long a_b;
}node[1010];
int read() {
int ans=0,flag=1;
char ch=getchar();
while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
if(ch=='-') flag=-1,ch=getchar();
while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans*flag;
}
void times(int x) {
memset(add,0,sizeof(add));
for(int i=1;i<=ans[0];i++) {
ans[i]=ans[i]*x;
add[i+1]+=ans[i]/10;
ans[i]%=10;
}
for(int i=1;i<=ans[0]+4;i++) {
ans[i]+=add[i];
if(ans[i]>=10) {
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
if(ans[i]!=0) {
ans[0]=max(ans[0],i);
}
}
return ;
}
int divition(int x) {
memset(add,0,sizeof(add));
int q=0;
for(int i=ans[0];i>=1;i--) {
q*=10;
q+=ans[i];
add[i]=q/x;
if(add[0]==0 && add[i]!=0) {
add[0]=i;
}
q%=x;
}
return 0;
}
bool compare() {
if(sum[0]==add[0]) {
for(int i=add[0];i>=1;i--) {
if(add[i]>sum[i]) return 1;
if(add[i]<sum[i]) return 0;
}
}
if(add[0]>sum[0]) return 1;
if(add[0]<sum[0]) return 0;
}
void cp () {
memset(sum,0,sizeof(sum));
for(int i=add[0];i>=0;i--) {
sum[i]=add[i];
}
return ;
}
bool cmp(Node a,Node b) {
return a.a_b<b.a_b;
}
int main() {
int n=read();
for(int i=0;i<=n;i++) {
node[i].a=read(),node[i].b=read();
node[i].a_b=node[i].a*node[i].b;
}
sort(node+1,node+n+1,cmp);
ans[0]=1,ans[1]=1;
for(int i=1;i<=n;i++) {
times(node[i-1].a);
divition(node[i].b);
if(compare()) {
cp();
}
}
for(int i=sum[0];i>=1;i--)
printf("%d",sum[i]);
return 0;
}
再看看俺们python
python 天下第一！！
学python就是为了水高精
N=int(input())
s=input().split()
S=int(s[0])
T=int(s[1])
a=[]#一个列表
for i in range(1,N+1):
k=input().split()
a.append((int(k[0]),int(k[1]))#列表里面套列表
a.sort(key=lambda x:x[0]*x[1])#按照左右数字乘积的大小来排序
ans=0
for i in range(0,N):
if(S//(a[i])[1]>ans):
ans=S//(a[i])[1]#S//(a[i])[1]其中//是取整除 - 返回商的整数部分（向下取整）
S*=(a[i])[0]
print(ans)
https://www.luogu.com.cn/problem/UVA1205
输入样例：
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
输出样例：
33
题解链接%%%打死我都想不出来QWQ
https://www.acwing.com/solution/AcWing/content/1065/
以下是题解截图：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef pair<double,double> PDD;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const int N=50010;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0
int n,m,r,ans;
struct node
{
int cnt,father,cost;//已合并的结点数，父节点，原始权值
double weight;//等效权值
}tree[N];
int find(){//找出等效权值点最大的节点
double maxW=0;
int res;
for(int i=1;i<=n;++i){
if(i!=r&&tree[i].weight>maxW){//特判不能是根节点
maxW=tree[i].weight;
res=i;
}
}
return res;
}
int main()
{
while(cin>>n>>r&&n+r>0){
ans=0;
over(i,1,n){
scanf("%d",&tree[i].cost);
tree[i].weight=tree[i].cost;
tree[i].cnt=1;
ans+=tree[i].cost;
}
over(i,1,n-1){
int a,b;
scanf("%d%d",&a,&b);
tree[b].father=a;
}
over(i,1,n-1){//执行n-1（除去根节点）
int pos = find();//找到最大等效权值点把他染色处理自己和其他点的状态
tree[pos].weight = 0;//重置等效权值，因为pos点已经被染过色了
int father = tree[pos].father;
ans+=tree[pos].cost*tree[father].cnt;
over(j,1,n){
if(pos==tree[j].father)
tree[j].father=father;//把pos的子节点合并到father上面
}
tree[father].cost+=tree[pos].cost;
tree[father].cnt+=tree[pos].cnt;
tree[father].weight=(double)tree[father].cost/tree[father].cnt;
}
printf("%d\n",ans);
}
return 0;
}
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号