贪心刷题小结

本文主要是介绍贪心刷题小结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

昨天晚上做LG秋令营题单时发现自己已经不会贪心了，所以就找了几道水题来练练手。

不是秋令营的题，我没有泄题

CF482A：（其实是构造？emmm分不清贪心与构造）若k=1，我们只需要按顺序输出就行了。k≠1呢？很自然的想到只需要在前k+1个数构造出k个差，后面直接顺序输出。因为k个差不能相等，所以我们可以一大一小的分配数字。即1,n,2,n-1...

代码：

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
il int read() {
    int s=0,w=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int N=1e5+5;
int n,k;
int main() {
    n=read(); k=read();
    int js=1,i=1,j=n;
    for(;js<=k;js++) {
        if(js % 2) {
            printf("%d ",i);
            i++;
        }
        else {
            printf("%d ",j);
            j--;
        }
    }
    if(js % 2) 
        for(;js<=n;js++) {
            printf("%d ",j); j--;
        }
    else {
        for(;js<=n;js++) {
            printf("%d ",i); i++;
        }
    }
    return 0;
}

CF545C：第一反应是按树高排序，优先倒低的的树，因为覆盖面积小所以期望收益大。但显然这样是错误的，因为树向左和向右倒的收益不同。那怎么办呢？换个思路，按位置排序，第一棵树向左倒，最后一棵树向右倒（这就不解释了）。对于中间的树，我们自然的想先让它向左倒，如果能到下的话，自然最优，如果不能倒下，我们再尽量让它向右倒。我们来分类讨论，如果第i棵树向右倒后，第i+1棵树还能向左倒，明显最优；如果第i+1棵树不能向左倒，此时我们若选择让第i棵树不倒而第i+1棵树向左倒，相比于直接让第i棵树向右倒，第i+1棵树失去了向右倒的机会，也就是说，这个方案劣于后者。这样，我们就证明了这个贪心的正确性。

代码：

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
il int read() {
    int s=0,w=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int N=1e5+10;
int n;
struct tree{
    int x,h;
} t[N];
bool cmp(tree a,tree b) { return a.x <b.x; }
int ans;
int main() {
    n=read();
    for(int i=1;i<=n;i++) t[i].x=read(),t[i].h=read();
    if(n==1) {
        printf("1");
        return 0;
    }
    sort(t+1,t+n+1,cmp);
    ans=2;
    for(int i=2;i<n;i++) {
        if(t[i].x - t[i].h > t[i-1].x) {
            ans++; continue;
        }
        if(t[i].x + t[i].h < t[i+1].x) {
            ans++; t[i].x+=t[i].h; continue;
        }
    }
    printf("%d\n",ans);
    return 0;
    
}

这篇关于贪心刷题小结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！