0x07 贪心

被虐爆了。。。贪心这种玄学东西还可以证吗？？除了范围缩放算是可以想想比较经典（倍增第一题？）。。。

poj3614：这道题想了很久，并没有想到是把minSPF按大到小排序，一直的思想是小的就小到大排序。后来仔细分析下，这题做法是n^2的，假如排序是要控制一个值的单调性，再用一个for来贪心，假如是小到大排序，选取时应该取大的还是应该取小的？直观上想选小的，因为后面的下界大，但是，假如当前位置区间很大而后一个很小就出问题了。假如是大到小排序，相当于逆过来，此时尽量取大，是基于当前的上界的，对于下界已经没有必要关注了，因为是单调递减的。考虑到这题没有权值，也可以看作全为1，当前的最大和后面的匹配无法得到更优解。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    int x,y;

}a[],b[];

bool cmp(node n1,node n2){return n1.x>n2.x;}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);

    for(int i=;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);

    sort(a+,a+n+,cmp);

    sort(b+,b+m+,cmp);

    int ans=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

            if(a[i].x<=b[j].x&&b[j].x<=a[i].y&&b[j].y>)

            {

                b[j].y--;ans++;

                break;

            }

    }

    printf("%d\n",ans);

    return ;

}

poj3614

poj3190：这题倒是没什么。。。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

struct node

{

    int x,y,z;

    friend bool operator>(node q1,node q2){return q1.y>q2.y;}

}a[];priority_queue< int,vector<node>,greater<node> >q;

bool cmp(node n1,node n2){return n1.x<n2.x;}

int bel[];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d%d",&a[i].x,&a[i].y), a[i].z=i;

    sort(a+,a+n+,cmp);

    int ans=;q.push(a[]);bel[a[].z]=;

    for(int i=;i<=n;i++)

    {

        node t=q.top();

        if(t.y<a[i].x)q.pop(),bel[a[i].z]=bel[t.z];

        else ans++,bel[a[i].z]=ans;

        q.push(a[i]);

    }

    printf("%d\n",ans);

    for(int i=;i<=n;i++)printf("%d\n",bel[i]);

    return ;

}

poj3190

poj1328：也算是小小的套路题吧。在越后放越好，“决策包容性”虽然运用的不是挺灵活，但是还蛮好想（所以这题难度在转换问题变成在n个区间里都要有至少一个点？？）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    double l,r;

}a[];

bool cmp(node n1,node n2)

{

    if(fabs(n1.l-n2.l)<1e-)return n1.r<n2.r;

    return n1.l<n2.l;

}

bool v[];

int main()

{

    int n,T_T=;double R;

    while(scanf("%d%lf",&n,&R)!=EOF)

    {

        if(n==&&R==)break;

        T_T++;

        double x,y;bool bk=true;

        for(int i=;i<=n;i++)

        {

            scanf("%lf%lf",&x,&y);

            if(y>R)bk=false;

            double dis=(sqrt((R*R)-(y*y)));

            a[i].l=x-dis;a[i].r=x+dis;

        }

        if(bk==false){printf("Case %d: -1\n",T_T);continue;}

        sort(a+,a+n+,cmp);

        int ans=;

        memset(v,false,sizeof(v));

        for(int i=;i<=n;i++)

        {

            if(v[i]==false)

            {

                ans++;v[i]=true;double pos=a[i].r;

                for(int j=i+;j<=n;j++)

                    if(a[j].l<=pos)v[j]=true,pos=min(pos,a[j].r);

                    else break;

            }

        }

        printf("Case %d: %d\n",T_T,ans);

    }

    return ;

}

poj1328

upd：我之前写的实在是太不优秀了。

把区间弄出来以后，相当于用最小的点覆盖所有区间，那么对于区间相互包含，不用管，对于区间分开没有交集，直接新开

那么就要处理覆盖一部分的情况。按L排序，决策包容，能选就选，L区间单调增，维护个R单调减，非法就新开

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node{double L,R;}a[];

bool cmp(node n1,node n2){return n1.L<n2.L;}

int main()

{

    int n,T_T=; double m,x,y;

    while(scanf("%d%lf",&n,&m)!=EOF)

    {

        if(n==&&m==)break;

        bool bk=true;

        for(int i=;i<=n;i++)

        {

            scanf("%lf%lf",&x,&y);

            if(y>m)bk=false;

            a[i].L=x-sqrt(m*m-y*y);

            a[i].R=x+sqrt(m*m-y*y);

        }

        if(bk==false){printf("Case %d: -1\n",++T_T);continue;}

        sort(a+,a+n+,cmp);

        int ans=;double R=a[].R;

        for(int i=;i<=n;i++)

        {

            if(a[i].L>R)

                ans++, R=a[i].R;

            else

                R=min(R,a[i].R);

        }

        printf("Case %d: %d\n",++T_T,ans);

    }

    return ;

}

poj1328(upd)

NOIP2012国王游戏：完全没有见过这种题型。。书上说微扰这个东西经常用于以排序为贪心策略的问题？反正这种数学东西证明，假如想到的话一般的还是不难推的。

顺便安利一道题bzoj3174: [Tjoi2013]拯救小矮人

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

int n,m;LL k;

LL a[],b[],tt[];

void mergesort(int l,int r)

{

    if(l==r)return ;

    int mid=(l+r)/;

    mergesort(l,mid);mergesort(mid+,r);

    int i=l,j=mid+,p=l;

    while(i<=mid&&j<=r)

    {

        if(b[i]<=b[j])tt[p++]=b[i++];

        else              tt[p++]=b[j++];

    }

    while(i<=mid)tt[p++]=b[i++];

    while(j<=r)  tt[p++]=b[j++];

    for(int i=l;i<=r;i++)b[i]=tt[i];

}

int clen;LL c[];

bool check(int l,int r)

{

    if(r>n)return false;

    int blen=r-l+;

    for(int i=l;i<=r;i++)b[i-l+]=a[i];

    mergesort(,blen);

    int i=,j=,p=;

    while(i<=blen&&j<=clen)

    {

        if(b[i]<=c[j])tt[p++]=b[i++];

        else              tt[p++]=c[j++];

    }

    while(i<=blen)tt[p++]=b[i++];

    while(j<=clen)tt[p++]=c[j++];

    p--;

    LL sum=;

    for(int i=;i<=m;i++)

    {

        if(p-i+<=i)break;

        sum+=(tt[p-i+]-tt[i])*(tt[p-i+]-tt[i]);

    }

    if(sum<=k)

    {

        clen=p;

        for(int i=;i<=clen;i++)c[i]=tt[i];

        return true;

    }

    else return false;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%lld",&n,&m,&k);

        for(int i=;i<=n;i++)scanf("%lld",&a[i]);

        int ed,ans=;

        for(int st=;st<=n;st=ed+)

        {

            ed=st;int L=;

            clen=;c[++clen]=a[st];

            while(L>)

            {

                if(check(ed+,ed+L)==true)

                {

                    ed=ed+L;

                    L*=;

                }

                else L/=;

            }

            ans++;

        }

        printf("%d\n",ans);

    }

    return ;

}

NOIP2012国王游戏

poj2054：这题是真的难啊，大开眼界。。。有一个性质，树中除根以外的最大点，一定会在它的父亲被染色之后被染色，那么居然依此来合并点。此时我们的目标是先把染色顺序给弄好，选择了放弃原本的权值转而自己定义新的权值！定义为合并包含的所有点的权值平均值。是可以数学归纳法证明的（这个东西不太会啊，我只用过来证柯西不等式。。。）具体做法我就是用链表存储顺序，然后用一个并查集维护合并了的块。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

int F[];

int findfa(int x)

{

    if(F[x]==x)return x;

    F[x]=findfa(F[x]);return F[x];

}

int u[],fa[];

struct node{int d,z;}c[];

bool v[];

int bef[],aft[],la[];

int main()

{

    int n,R;

    while(scanf("%d%d",&n,&R)!=EOF)

    {

        if(n==&&R==)break;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&c[i].d);u[i]=c[i].d;

            c[i].z=;F[i]=i;

            bef[i]=aft[i]=-;la[i]=i;

        }

        int x,y;

        for(int i=;i<n;i++)

            scanf("%d%d",&x,&y), fa[y]=x;

        memset(v,false,sizeof(v));v[R]=true;

        for(int i=;i<n;i++)

        {

            int id=-;

            for(int j=;j<=n;j++)

                if(v[j]==false)

                    if(id==-||c[id].d*c[j].z<c[j].d*c[id].z)id=j;

            v[id]=true;

            int truefa=findfa(fa[id]);F[id]=truefa;

            c[truefa].d+=c[id].d;

            c[truefa].z+=c[id].z;

            bef[id]=la[truefa];

            aft[la[truefa]]=id;

            la[truefa]=la[id];

        }

        LL ans=;

        for(int i=;i<=n;i++)

            ans+=(LL(i))*(LL(u[R])), R=aft[R];

        printf("%lld\n",ans);

    }

    return ;

}

poj2054

巴特西

0x07 贪心

最新文章

热门文章