首页 > 其他 > 详细

CF545C

时间:2019-10-24 19:39:56      阅读:61      评论:0      收藏:0      [点我收藏+]

给 n 棵树在一维数轴上的坐标,以及它们的?度。现在要你砍倒 这些树,树可以向左倒也可以向右倒,砍倒的树不能重合、当然 也不能覆盖其他的树原来的位置,现在求最?可以砍倒的树的数 目。 1 ≤ n ≤ 10^5 , 1 ≤ xi , hi ≤ 10^9

 

思路:贪心:能往左倒就尽量往左倒,否则就往又倒,证明:

首先对于一颗树,如果他能往左边倒下,对于后面的每一颗树没有任何影响,所以往左边倒必定是优的。

如果不能往左边倒而是要往右边倒下,考虑代价和贡献:

贡献:答案+1;

代价:由于不能越过右边的第一颗树,所以最坏的结果是右边的第一颗树不能倒下,代价最多是 -1 ;

在贪心中,只要一种贪心策略能够让答案不会变差,那么这个贪心策略就是最优秀的,而我们的贪心策略中最坏的结果是贡献和代价相抵消,所以答案必定是最优的;

 

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define maxn 100010
#define ll long long
#define IL inline
#define clear(a) memset(a,0,sizeof a)

ll n,ans;
struct edge{
    ll id,h,lef,rig;
}e[maxn];

IL void read(ll &x){
    x=0;int f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-)f=-f;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0,ch=getchar();}x*=f;
}

int main()
{
    read(n);
    for(int i=1;i<=n;i++)
        read(e[i].id),read(e[i].h);
    for(int i=1;i<=n;i++){
        if(i==1)e[i].lef=1e14,e[i].rig=e[i+1].id-e[i].id-1;
        else if(i==n)e[i].lef=e[i].id-e[i-1].id-1,e[i].rig=1e14;
        else e[i].lef=e[i].id-e[i-1].id-1,e[i].rig=e[i+1].id-e[i].id-1;
    }
    for(int i=1;i<=n;i++){
        if(e[i].lef>=e[i].h)
            ans++,e[i-1].rig-=e[i].h;
        else if(e[i].lef<e[i].h&&e[i].rig>=e[i].h)
            ans++,e[i+1].lef-=e[i].h;
    }
    cout<<ans<<"\n";
    return 0;
}

 

CF545C

原文:https://www.cnblogs.com/KGW-/p/11733941.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!