贪心刷题小结

昨天晚上做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;
    
}

 

上一篇:2021.10.19 离散化模板


下一篇:【23种GOF设计模式】C#代码完整案例详解--抽象工厂