算法总结—贪心1

· · 算法·理论

记住一点：贪心是应用于那些只需要做出在当前是最优的选择就能获得整体最优结果的问题上，它一般需要与排序或优先队列(即二叉堆)配合使用。

1.\tt Koszulki

题目给了我们一小段公式其中 ∃ 表示存在的意思。

思路

题目其实就是让我们求有多少个数是大于等于从大往小第 k 个数的，我们从大到小排个序，在一个个找是否满足要求即可。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int a[2005];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,greater<int>());
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=a[k]){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

2. 部分背包问题

这题的关键就在于这里的物品可以任意分割 。

所以我们只需要把装的下的放入背包，装不下的分割再放入背包，由于可以分割，所以我们是按每个物品的性价比排序，其中性价比等于价值除以质量。

代码

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int w,v;
    double pj;//记得开double
}a[105];
bool cmp(node q,node h){
    return q.pj>h.pj;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].w>>a[i].v;
        a[i].pj=(a[i].v*1.00/a[i].w);//求性价比
    }
    sort(a+1,a+1+n,cmp);
    double cnt=0;
    double ans=0;
    for(int i=1;i<=n;i++){
        if(cnt+a[i].w<=m){//试探性的看能不能装下
            cnt+=a[i].w;
            ans+=a[i].v;
        }else{//装不下就根据比例分割
            int t=m-cnt;
            double tt=double(t)/a[i].w;
            ans+=a[i].v*tt;
            break;
        }
    }
    printf("%.2lf",ans);
    return 0;
}

3. 骑士的工作

这道题的贪心策略很容易就想到了，就是用能力小的骑士砍体积(大小)小的头，用能力大的骑士砍体积(大小)大的头。

我们可以用 for 循环枚举每一个龙头，再用一个指针 j 指向当前砍龙头的骑士，如果 j 号骑士砍不断第 i 个龙头 (a_i>b_j) ,j 加一，否则，答案加上 b_j，j 也加上一，因为一个骑士最多只能砍一个龙头。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int a[20005],b[20005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    int j=1;
    int ans=0;
    for(int i=1;i<=n;i++){
        while(j<=m&&a[i]>b[j]){
            j++;
        }
        if(j>m){
            cout<<"you died!";
            return 0;
        }
        ans+=b[j];
        j++;
    }
    cout<<ans;
    return 0;
}

4.刷题

这道题虽然是道贪心，但主要不是贪心啊，这道题的主要考点就是计算时间差。

我们计算两个时间点的时间差时可以先算出一个时间点距离公元 0 年的单位时间，再算出另一个时间点距离公元 0 年的单位时间，再将这两个数值相减即可。具体计算方法见此。

贪心策略

要在一定时间内刷更多的题，每道题的时间就要尽可能地少，所以我们把做题时间从小到大排个序即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int a[5005];
int mon[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int run(int x){
    return ((x%4==0&&x%100!=0||x%400==0)?366:365);
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int year1,month1,day1,hour1,minute1;
    scanf("%lld-%lld-%lld-%lld:%lld",&year1,&month1,&day1,&hour1,&minute1);
    int year2,month2,day2,hour2,minute2;
    scanf("%lld-%lld-%lld-%lld:%lld",&year2,&month2,&day2,&hour2,&minute2);
    int x=0;
    for(int i=0;i<year1;i++){
        x+=run(i)*1440;
    } 
    for(int i=1;i<month1;i++){
        x+=((run(year1)==366&&i==2)?29:mon[i])*1440;
    }
    x+=(day1-1)*1440+hour1*60+minute1;
    int y=0;
    for(int i=0;i<year2;i++){
        y+=run(i)*1440;
    } 
    for(int i=1;i<month2;i++){
        y+=((run(year2)==366&&i==2)?29:mon[i])*1440;
    }
    y+=(day2-1)*1440+hour2*60+minute2;
    int cnt=y-x;
    int k=0;
    for(int i=1;i<=n;i++){
        k+=a[i];
        if(k>cnt){
            cout<<i-1;
            return 0;
        }
    }
    cout<<n;
    return 0;
}

5.\tt Competition

贪心策略：

我们把 a_i 和 b_i 相减，再对这个差进行排序，最后让前 b 个去打生物竞赛，其他人去打物理竞赛。

一道思维题。

代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
struct node{
    int a,b,c;
}a[100005];
bool cmp(node q,node h){
    return q.c<h.c;
}
bool vis[100005];
signed main(){
    int n,x,y;
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++){
        cin>>a[i].a;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].b;
        a[i].c=a[i].a-a[i].b;
    }
    sort(a+1,a+1+n,cmp);
    int ans=0;
    for(int i=1;i<=y;i++){
        ans+=a[i].b;
        vis[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]){
            continue;
        }
        ans+=a[i].a;
    }
    cout<<ans;
    return 0;
}