贪心:求最优性问题方法
Question 01 [区间选点]
有 n 个区间,每个区间至少有一个点
求至少需要几个点
Answer 01
右端点升序排序
若左端点已被覆盖便略过
否则选当前区间右端点
Code
同Q2 Code
exCode ACP2033 [种树]
树可能有多棵，均放在右侧把后面布满即可
注意右侧摆放的位置可能有tree
需要进行特判
#include<bits/stdc++.h>
using namespace std;
const int N=88500;
struct range{int l,r,key;}k[N];
int n,tmp;
bool tree[N];
bool cmp(range A,range B){return A.r<B.r;}
int tree_num(int id,int rim){
int tot=0;
for(int i=k[id].l;i<=rim;i++)if(tree[i])++tot;
return tot;
}
int main(){
scanf("%d%d",&tmp,&n);
for(int i=1;i<=n;i++)scanf("%d%d%d",&k[i].l,&k[i].r,&k[i].key);
sort(k+1,k+n+1,cmp);
int ans=0,rim=-1999;
for(int i=1;i<=n;i++){
int w=k[i].key-tree_num(i,rim),it=k[i].r;
while(w>0){
if(tree[it]){--it;continue;}
tree[it]=true;
--w,++ans;
}
rim=k[i].r;
}
printf("%d",ans);
return 0;
}
Question 02 [区间选择]
有n个区间,选取尽量多个区间使所取区间两两不相交。
Answer 02
右端点升序排序
若左端点已被覆盖便略过
否则更新右端点限制
实际上和 Question 01 是一样的
Code
#include<bits/stdc++.h>
using namespace std;
struct range{int l,r;}k[1024];
int n;
bool cmp(range A,range B){return A.r<B.r;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&k[i].l,&k[i].r);
sort(k+1,k+n+1,cmp);
int t=-1918,ans=0;
for(int i=1;i<=n;i++){
if(t>=k[i].l)continue;
++ans,t=k[i].r;
}
printf("%d",ans);
return 0;
}
exCode ACP2032 [活动安排]
注意左闭右开
#include<bits/stdc++.h>
using namespace std;
struct range{int l,r;}k[1024];
int n;
bool cmp(range A,range B){return A.r<B.r;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&k[i].l,&k[i].r);
sort(k+1,k+n+1,cmp);
int t=-1918,ans=0;
for(int i=1;i<=n;i++){
if(t>=k[i].l)continue;
++ans,t=k[i].r;
}
printf("%d",ans);
return 0;
}
Question 03 [区间覆盖]
选择最少区间以覆盖大区间
Answer
左端点排序
选择能覆盖当前大区间左端点且右端点最靠后的区间
更新左端点
直到没有区间能覆盖当前大区间左端点或区间覆盖完成为止
Code
#include<bits/stdc++.h>
using namespace std;
const int N=100098;
struct range{int l,r;}k[N];
int n,lim,rim;
bool cmp(range a,range b){
return a.l<b.l;
}
int main(){
scanf("%d%d%d",&lim,&rim,&n);
for(int i=1;i<=n;i++)scanf("%d%d",&k[i].l,&k[i].r);
sort(k+1,k+n+1,cmp);
int best,bid,tmp=0,ans=0;
while(lim<rim){
bid=0,best=lim;
for(int i=tmp+1;i<=n;i++){
if(k[i].l>lim)break;
if(k[i].r>best)bid=i,best=k[i].r;
}
if(bid==0){puts("-1"),exit(0);}
lim=best;
tmp=bid;
++ans;
}
printf("%d",ans);
return 0;
}
exCode ACP2034 [喷水装置]
易见只有中间的长方形区域才是有效覆盖
其余部分会有遗漏
所以半径小于等于宽度一半的可以直接舍掉
(半径等于宽度一半有效覆盖只有一条线)
勾股求出有效范围后直接套板子
#include<bits/stdc++.h>
using namespace std;
const int N=15009;
struct range{double l,r;}k[N];
bool cmp(range A,range B){return A.l<B.l;}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T,n_pre,n,ans,best_id,last_qid;
double W,lim,rim,pos,r,best_key;
cin>>T;
while(T--){
lim=0.0,n=0,ans=0,last_qid=0;
cin>>n_pre>>rim>>W;
for(int i=1;i<=n_pre;i++){
cin>>pos>>r;
if(r*2.0-W<1e-6)continue;
k[++n]={pos-sqrt(r*r-W*W*0.25),pos+sqrt(r*r-W*W*0.25)};
}
sort(k+1,k+n+1,cmp);
while(rim>lim){
best_id=-1,best_key=lim;
for(int i=last_qid+1;i<=n;i++){
if(k[i].l>lim)break;
if(k[i].r>best_key)best_key=k[i].r,best_id=i;
}
if(best_id==-1){cout<<"-1\n";goto fuck;}
last_qid=best_id;
++ans;
lim=best_key;
}
cout<<ans<<"\n";
fuck:;
}
return 0;
}
Question 04 [区间分组]
有n个区间,分成尽量少组使得每组中区间两两不相交
Answer
左端点正序排序
如果暂无分组或当前左端点小于所有组右端点最小值则新开一组
否则由于左端点正序
插入任意组均可,便插入最小值组
每组仅记录右端点
用堆取最小值即可
Code
#include<bits/stdc++.h>
using namespace std;
const int N=100067;
int n;
priority_queue<int,vector<int>,greater<int> > q;
struct range{int l,r;}k[N];
bool cmp(range a,range b){return a.l<b.l;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&k[i].l,&k[i].r);
sort(k+1,k+n+1,cmp);
for(int i=1;i<=n;i++){
if(q.empty()||k[i].l<=q.top())q.push(k[i].r);
else q.pop(),q.push(k[i].r);
}
printf("%d",q.size());
return 0;
}
Question 05 [ACP2035 双路加工]
有 n 个任务,每个任务都需要被两个机器完成分别需要 A[i],B[i]时刻
必须先用 A 机器完成再用 B 机器完成
求所需最低时间
Answer
本题答案抽象
方法如下
将 n 个任务按 min(a,b) 正序排序
进行遍历
若 a<=b 则将其插入当前的前部
若 a>b 则将其插入当前的后部
得到任务完成的顺序
example:
n=5
A: 3 5 8 7 10
B: 6 2 1 4 9
--------sort---------
A: 8 5 3 7 10
B: 1 2 6 4 9
id:1 2 3 4 5
-------order-------
log01:[ |1]
log01:[ |2 1]
log01:[3|2 1]
log01:[3|4 2 1]
log01:[3|5 4 2 1]
然后模拟加工
Time(B机器完成第 i 个任务)=Time(第 i 个任务花费B)+max(Time(B机器完成第 i-1 个任务),Time(A 机器完成第 i 个任务))
Time(B机器完成第 i-1 个任务)------------->B 已经完成
Time(A机器完成第 i 个任务)--------------->任务可以加工
Code
#include<bits/stdc++.h>
using namespace std;
int n,order[1045];
struct task{int A=0,B=0;}k[1045];
bool cmp(task a,task b){return min(a.A,a.B)<min(b.A,b.B);}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&k[i].A);
for(int i=1;i<=n;i++)scanf("%d",&k[i].B);
sort(k+1,k+n+1,cmp);
int ff=0,tt=n+1;
for(int i=1;i<=n;i++){
if(k[i].A<k[i].B){
order[++ff]=i;
}else{
order[--tt]=i;
}
}
int BB=0,timer=0;
for(int i=1;i<=n;i++){
timer+=k[order[i]].A;
BB=max(BB,timer)+k[order[i]].B;
}
printf("%d",BB);
return 0;
}
Question 06 [ACP2042 糖果传递]
有 n 个小朋友坐成一圈
每人有一定糖果
每人只能给左右两人传递糖果
求使所有人糖果数相同的最小传递次数
Answer
推式子题
设i给i-1个数为give[i]个(give[1]为 1 给 n 的个数)
所求为|give[1]|+|give[2]|+...+|give[n]|最小值
具体推导过程见Code
最终这一坨化为
|pos[1]-c[1]|+|pos[1]-c[2]|+...+|pos[1]-c[n]|
其中 c 数组为已得
根据初中绝对值知识
pos[1]取{ c[n/2+1] (n%2==1) }时原式最小
{ c[n/2] to c[n/2+1] (n%2==0) }
所以统计答案即可
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1000908;
int n;
long long lable[N],average,c[N];
long long llabs(long long ll){
if(ll>0)return ll; return ll*-1ll;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&lable[i]),average+=lable[i];
average/=(long long)n;
c[n]=average-lable[n];
for(int i=n-1;i>=1;i--)c[i]=c[i+1]+average-lable[i];
sort(c+1,c+n+1);
long long give01=c[(n+1)/2],ans=0;
for(int i=1;i<=n;i++)ans+=llabs(c[i]-give01);
printf("%lld",ans);
return 0;
}
//give[i] i gives i-1 (1 gives n)
//lable[1]-give[1]+give[2]=average -> give[1]-give[2]=lable[1]-average =>give[1]=give[1]-0 so key[1]=0
//lable[2]-give[2]+give[3]=average -> give[2]-give[3]=lable[2]-average
//...
//lable[i]-give[i]+give[i+1]=average -> give[i]-give[i+1]=lable[i]-average =>give[i]=give[1]-(key[i+1]+average-lable[i])
//...
//lable[n-1]-give[n-1]+give[n]=average -> give[n-1]-give[n]=lable[n-1]-average => give[n-1]=give[1]-(2*average-lable[n]-lable[n-1])=give[1]-(key[n]+average-lable[n-1])
//lable[n]-give[n]+give[1]=average -> give[n]-give[1]=lable[n]-average => give[n]=give[1]-(average-lable[n])
// -------------------
// into key [n]
Question 07 [ACP2041 钓鱼]
www.accoders.com/problem.php?cid=5014&pid=5
Answer
考虑枚举只经过前几个池塘
显然一定不走回头路最优
接下来就是贪心
我们想要在当前的5min中在目前鱼量最大的池塘钓鱼
用堆维护,每次弹堆顶并更新
注意时间有可能走不到最后的池塘
特判即可
Code
#include<bits/stdc++.h>
using namespace std;
const int N=9999;
int n,leisure,fish[N],delta[N],trip[N],ans,answer=-1;
struct node{
int id,key;
bool operator <(const node &rhs)const{
return key<rhs.key;
}
};
int main(){
scanf("%d%d",&n,&leisure);
leisure*=12;// 1 hour=12 five min
node t;
for(int i=1;i<=n;i++)scanf("%d",&fish[i]);
for(int i=1;i<=n;i++)scanf("%d",&delta[i]);
for(int i=1;i<n;i++)scanf("%d",&trip[i]),trip[i]+=trip[i-1];
for(int i=1,left_time;i<=n;i++){
ans=0;
priority_queue<node> q;
left_time=leisure-trip[i-1];
if(left_time<=0)break;
for(int j=1;j<=i;j++)q.push({j,fish[j]});
while(left_time--){
t=q.top(),q.pop();
if(t.key<0)break;
ans+=t.key;
q.push({t.id,t.key-delta[t.id]});
}
answer=max(answer,ans);
}
printf("%d",answer);
return 0;
}
Question 08 [ACP2036 智力大波浪]
n 个时段,每个时段完成一个任务,计时从1 开始
每个任务都有截止日期和无法完成的代价
求最小代价
Answer
将任务代价从大到小排序
尽量后完成
完成不了就记录代价
Code
#include<bits/stdc++.h>
using namespace std;
const int N=900;
int money,n;
bool st[1008];
struct task{int deadline,beat;}k[N];
bool cmp(task a,task b){return a.beat>b.beat;}
int main(){
int die=-1,it;
scanf("%d%d",&money,&n);
for(int i=1;i<=n;i++)scanf("%d",&k[i].deadline);
for(int i=1;i<=n;i++)scanf("%d",&k[i].beat);
sort(k+1,k+n+1,cmp);
for(int i=1;i<=n;i++){
it=k[i].deadline;
if(it<=die){money-=k[i].beat;continue;}
while(it>0&&st[it])--it;
if(it==0){money-=k[i].beat,die=k[i].deadline;continue;}
st[it]=true;
}
printf("%d",money);
return 0;
}
