一本通第一章-贪心算法 题解

题解 算法-贪心 题目-一本通
题目链接 编辑文章

徐妈让我们做一本通的题,说是巩固基础。但说实话这里面的题又烂又水,就连第一章11道题就有双倍经验我也是无语的。

这一章完成时间:两天(其实就是一个晚自习1h+两个中午40min),而且还包括颓废时间

10000.活动安排

贪心区间覆盖经典模型。按照右端点排序,然后依次判断能不能放即可。

struct Edge{
    int s,f;
} edge[1005];
int n,ans;

inline bool cmp(Edge x,Edge y)
{
    return (x.f==y.f) ? x.s>y.s : x.f<y.f;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) edge[i].s=read(),edge[i].f=read();
    sort(edge+1,edge+n+1,cmp);
    int last=0;
    for (int i=1;i<=n;i++)
    {
        if (edge[i].s<last) continue;
        ans++;
        last=edge[i].f;
    }
    printf("%d",ans);
    return 0;
}

10001.种树

还是贪心经典模型。按右端点排序,对于每一次询问将不够的树尽量放右端点即可。

struct Edge{
    int s,f,sum;
} edge[5005];
bool have_tree[30005];
int n,m,ans;

inline bool cmp(Edge x,Edge y)
{
    return (x.f==y.f) ? x.s<y.s : x.f<y.f;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++) edge[i].s=read(),edge[i].f=read(),edge[i].sum=read();
    sort(edge+1,edge+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
        int now=0;
        for (int j=edge[i].s;j<=edge[i].f;j++) now+=have_tree[j];
        if (now>=edge[i].sum) continue;
        now=edge[i].sum-now;
        int j=edge[i].f+1;
        while (now)
        {
            j--;
            if (have_tree[j]) continue;
            have_tree[j]=1;
            ans++;
            now--;
        }
    }
    printf("%d",ans);
    return 0;
}

10002.喷水装置

很容易看出,每个圆能覆盖的范围的边界只是与矩形相交的两点连接成的割线。我们已知圆半径 $R$ 和矩形的宽度 $W$ ,那么很容易得出圆心到能覆盖范围边界的距离为 $R^{2} - \left( \dfrac {W}{2}\right) ^{2}$。

这样就得到了每个圆覆盖的左右边界,就可以把这些圆看成线段然后转化成经典的贪心线段全覆盖问题了。按照左端点排序,在每一个左端点 $<=$ 当前已覆盖的最右端点的线段中选一个右端点最大的,直到放到终点。

struct Edge{
    double st,ed;
} edge[15005];
int n,l,w,a,b,t;

inline bool cmp(Edge x,Edge y)
{
    return (x.st==y.st) ? x.ed>y.ed : x.st<y.st;
}

int main()
{
    t=read();
    while (t--)
    {
        int cnt=0,ans=0;
        n=read(); l=read(); w=read();
        for (int i=1;i<=n;i++)
        {
            a=read(); b=read();
            if (b*2<=w) continue;
            double len=sqrt(1.0*b*b-1.0*w*w/4.0);
            edge[++cnt].st=a-len;
            edge[cnt].ed=a+len;
        }
        n=cnt;
        sort(edge+1,edge+n+1,cmp);
        double last=0;
        int i=1;
        while (i<=n && last<l)
        {
            double mx=-1;
            while (edge[i].st<=last && i<=n)
            {
                mx=max(mx,edge[i].ed);
                i++;
            }
            if (mx==-1) break;
            last=mx;
            ans++;
        }
        if (last<l) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}

10003.加工生产调度

洛谷P1248 加工生产调度

那个啥,感觉要解释正确的排序方法感觉有点复杂,我就直接用个洛谷的题解吧: https://www.luogu.org/blog/79017/solution-p1248

struct node{
    int a,b,d,id;
} s[1005];
int n,m,ans;

inline bool cmp(node x,node y)
{
    return (x.d==y.d) ? (x.d<=0) ? x.a<y.a : x.b>y.b : x.d<y.d;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].a=read(),s[i].id=i;
    for (int i=1;i<=n;i++) s[i].b=read(),s[i].d=(s[i].a==s[i].b) ? 0 : (s[i].a<s[i].b) ? -1 : 1;
    sort(s+1,s+n+1,cmp);
    int gap=s[1].a,nowb=s[1].b,ans=s[1].b,add=0;
    for (int i=2;i<=n;i++)
    {
        if (s[i].a>=add) s[i].a-=add,add=0;
        else add-=s[i].a,s[i].a=0; 
        if (s[i].a>nowb) gap+=s[i].a-nowb;
        else add+=nowb-s[i].a;
        nowb=s[i].b;
        ans+=s[i].b;
    }
    ans+=gap;
    printf("%d\n",ans);
    for (int i=1;i<=n;i++) printf("%d ",s[i].id);
    return 0;
}

10004.智力大冲浪

洛谷P1230 智力大冲浪

很容易想到,肯定要先完成扣款多的,所以我们按照扣款进行排序。而对于每一个可以完成的,我们肯定要把它尽量往后放。

int n,m,ans;
struct node{
    int t,w;
} s[505];
bool vis[505];

inline bool cmp(node x,node y)
{
    return x.w>y.w;
}

int main()
{
    m=read(); n=read();
    for (int i=1;i<=n;i++) s[i].t=read();
    for (int i=1;i<=n;i++) s[i].w=read();
    sort(s+1,s+n+1,cmp);
    for (int i=1;i<=n;i++)
    {
        int j=s[i].t;
        while (j && vis[j]) j--;
        if (!j) ans+=s[i].w;
        else vis[j]=1;
    }
    printf("%d",m-ans);
    return 0;
}

10005.数列极差

手算一下可以发现,先算小后算大得到的答案大,先大后小的答案小。

具体的证明我就不推了,不过很显然,加上的每一个1只对后面的答案有贡献,所以后面自然越大越好。

int n,m;
priority_queue <int,vector<int>,greater<int> > q1;
priority_queue <int> q2;

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        m=read();
        q1.push(m);
        q2.push(m);
    }
    m=read();
    while (!q1.empty())
    {
        int x=q1.top(); q1.pop(); 
        if (q1.empty())
        {
            m=x;
            break;
        }
        int y=q1.top(); q1.pop();
        q1.push(x*y+1);
    }
    while (!q2.empty())
    {
        int x=q2.top(); q2.pop(); 
        if (q2.empty())
        {
            m=m-x;
            break;
        }
        int y=q2.top(); q2.pop();
        q2.push(x*y+1);
    }
    printf("%d",m);
    return 0;
}

10006.数列分段

洛谷P1181 数列分段Section I

红题。。。这个还用写吗?

int n,m,a;

int main()
{
    n=read(); m=read();
    int sum=0,cnt=1;
    for (int i=1;i<=n;i++)
    {
        a=read();
        if (sum+a<=m) sum+=a;
        else cnt++,sum=a;
    }
    printf("%d",cnt);
    return 0;
}

10007.线段

与10000重题,垃圾ybt。

struct Edge{
    int s,f;
} edge[1000005];
int n,ans;

inline bool cmp(Edge x,Edge y)
{
    return (x.f==y.f) ? x.s>y.s : x.f<y.f;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) edge[i].s=read(),edge[i].f=read();
    sort(edge+1,edge+n+1,cmp);
    int last=0;
    for (int i=1;i<=n;i++)
    {
        if (edge[i].s<last) continue;
        ans++;
        last=edge[i].f;
    }
    printf("%d",ans);
    return 0;
}

10008.家庭作业

看起来和智力大冲浪差不多,但很显然数据范围要大一些,但ybt烂就烂在朴素做法都能得80

所以我们可以按照时间排序,用优先队列(小根堆)维护,如果能够完成就入队,如果不能完成但价值比队头大就替换掉队头。

struct les{
    int t,v;
} s[1000005];
int n,ans;
priority_queue <int,vector<int>,greater<int> > q;

inline bool cmp(les x,les y)
{
    return x.t<y.t;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].t=read(),s[i].v=read();
    sort(s+1,s+n+1,cmp);
    int t=1;
    for (int i=1;i<=n;i++)
    {
        if (s[i].t>=t) 
        {
            q.push(s[i].v);
            t++;
        }
        else if (s[i].v>q.top())
        {
            q.pop();
            q.push(s[i].v);
        }
    }
    while (!q.empty())
    {
        ans+=q.top();
        q.pop();
    }
    printf("%d",ans);
    return 0;
}

10009.钓鱼

洛谷P1717 钓鱼

这道有点难想,我又没注意到这个小的数据范围,所以看题解前毫无思路。

如果限制了到哪个湖停下来,那么这道题就很容易了。首先走路的时间确定了剩下的时间也就确定了,然后开个优先队列(大根堆),每次取队头元素,计算贡献后减去鱼的减少值再入队,直到了时间耗完了就得到答案了。

因为这道题的数据范围小,所以我们可以枚举在哪个点停下来,最后取一个最大值就行了。

#define pr pair<int,int>
#define mp make_pair

int n,h,ans,t[105],v[105],d[105];

int main()
{
    n=read(); h=read()*12;
    for (int i=1;i<=n;i++) v[i]=read();
    for (int i=1;i<=n;i++) d[i]=read();
    for (int i=2;i<=n;i++) t[i]=read();
    for (int i=1;i<=n;i++)
    {
        h-=t[i];
        priority_queue <pr> q;
        for (int j=1;j<=i;j++) q.push(mp(v[j],d[j]));
        int now=0;
        for (int j=1;j<=h;j++)
        {
            pr x=q.top(); q.pop();
            if (x.first<=0) break;
            now+=x.first;
            x.first-=x.second;
            q.push(x);
        }
        ans=max(ans,now);
    }
    printf("%d",ans);
    return 0;
}

10010.糖果传递

四倍经验:洛谷P2512 糖果传递UVa11300洛谷P4016 负载平衡问题

用 $f[]$ 记录糖果的前缀和,然后枚举断点 $x$ 断环成链,剩下的就按照均分纸牌的思路做,可以得到最小花费为:

$$ans= \sum ^{n}_{i=1}\left| f\left[ i\right] -f\left[ x\right] \right| $$

很显然,$x$ 取中位数时答案最小。

ll n,ans,s[1000005],f[1000005];

int main()
{
    n=read();
    ll sum=0;
    for (int i=1;i<=n;i++) s[i]=read(),sum+=s[i];
    sum/=n;
    for (int i=1;i<=n;i++) f[i]=f[i-1]+s[i]-sum;
    sort(f+1,f+n+1);
    int mid=(n+1)>>1;
    for (int i=1;i<=n;i++) ans+=abs(f[i]-f[mid]);
    printf("%lld",ans);
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空