洛谷 P1484/P1792/P3620 种树/数据备份 题解【堆】【贪心】

作者: wjyyy 分类: ,数据结构,解题报告,贪心 发布时间: 2018-09-07 10:23

点击量:17

 

    这个题妥妥的三倍经验啊……只贴一个题面好了。

 

题目描述

A城市有一个巨大的圆形广场,为了绿化环境和净化空气,市政府决定沿圆形广场外圈种一圈树。

 

园林部门得到指令后,初步规划出\(n\)个种树的位置,顺时针编号\(1\)到\(n\)。并且每个位置都有一个美观度\(A_i\),如果在这里种树就可以得到这\(A_i\)的美观度。但由于A城市土壤肥力欠佳,两棵树决不能种在相邻的位置(\(i\)号位置和\(i+1\)号位置叫相邻位置。值得注意的是\(1\)号和\(n\)号也算相邻位置!)。

 

最终市政府给园林部门提供了\(m\)棵树苗并要求全部种上,请你帮忙设计种树方案使得美观度总和最大。如果无法将\(m\)棵树苗全部种上,给出无解信息。

 

输入输出格式

输入格式:

输入的第一行包含两个正整数\(n,m\)。第二行\(n\)个整数\(A_i\)。

 

输出格式:

输出一个整数,表示最佳植树方案可以得到的美观度。如果无解输出“Error!”,不包含引号。

 

输入输出样例

输入样例#1:

7 3
1 2 3 4 5 6 7
输出样例#1:

15
输入样例#2:

7 4
1 2 3 4 5 6 7
输出样例#2:

Error!

说明

对于全部数据:\(m\le n\);

\(-1000\le A_i\le 1000\)

N的大小对于不同数据有所不同:

数据编号 N的大小 数据编号 N的大小
1 30 11 200
2 35 12 2007
3 40 13 2008
4 45 14 2009
5 50 15 2010
6 55 16 2011
7 60 17 2012
8 65 18 199999
9 200 19 199999
10 200 20 200000

题解:

    这其实是一道堆优化的题,需要先推一个贪心结论,剩下的难点就是代码实现。应该这些不能取相邻元素的题,都可以用这种方法做了吧。

 

    一开始可能会想,我把所有树排序,每次选最大的,如果左右有被选过的就不选,但是这样就不能保证合法且最优了。比如说这样的数据:

4 2
4 5 4 0

    如果上来就选择5,那么两个4就不能选了,所以不能直接从大的选。但是我们可以证明,如果最大的不选,那么这棵树两边的树都得选。否则只选一个,并没有选中间的这个对答案的贡献大,而且选择中间这个对选择其他的树的影响更小。如下图:

    而如果同时选上两边的,虽然会对外侧有影响,但是产生的贡献会比单个5多,因此可以考虑备选。但是这样就有选择了,貌似转化为了一个DP问题。不过实际上,选择了两个4,就多选了1个,这三个位置可以转化为:选1个的贡献是5,选2个的贡献是8。而本身选了5,两个4就不能选,那么我们就可以在选择了5之后把4,5,4合并起来,作为一个新的节点,贡献为3,原本的5可以直接计入答案,进行下一个子问题。

 

    这样就变成了贪心问题,每次选择序列中贡献最大的节点,合并它及左右的两个为一个节点。维护序列用链表就可以了,维护贡献最大的点可以用堆。不过被合并的点要从堆中删除,这里数据范围都不大,用懒惰删除就可以了。

 

    种树这个题是环形,在输入完毕后把链表首尾相连就可以了。而另外两个题需要注意左右边界问题。

 

Code of 种树:

#include<cstdio>
#include<cstring>
struct node
{
    node *pre,*nxt;
    long long key;
    bool del;
    node(long long key)
    {
        this->key=key;
        del=0;
        pre=NULL;
        nxt=NULL;
    }
    node()
    {
        del=0;
        pre=NULL;
        nxt=NULL;
    }
}*head,*heap[200100];
int l=0;
void push(node *x)//指针好像放不进stl的优先队列
{
    heap[++l]=x;
    int i=l;
    node *tmp;
    while(i>1&&heap[i]->key>heap[i>>1]->key)
    {
        tmp=heap[i];
        heap[i]=heap[i>>1];
        heap[i>>1]=tmp;
        i>>=1;
    }
    return;
}
void pop()
{
    heap[1]=heap[l--];
    int i=1;
    node *tmp;
    while((i<<1)<=l&&(heap[i]->key<heap[i<<1]->key||heap[i]->key<heap[i<<1|1]->key))
        if((i<<1)==l||heap[i<<1]->key>heap[i<<1|1]->key)
        {
            tmp=heap[i];
            heap[i]=heap[i<<1];
            heap[i<<1]=tmp;
            i<<=1;
        }
        else
        {
            tmp=heap[i];
            heap[i]=heap[i<<1|1];
            heap[i<<1|1]=tmp;
            i=i<<1|1;
        }
    return;
}
node *Insert(node *p,long long x)//在链表的p后面插入x元素
{
    node *tmp=new node(x);
    tmp->pre=p;
    tmp->nxt=p->nxt;
    p->nxt->pre=tmp;
    p->nxt=tmp;
    return tmp;
}
void Delete(node *p)
{
    p->del=1;
    p->pre->nxt=p->nxt;
    p->nxt->pre=p->pre;
}
int a[201000];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(2*m>n)
    {
        puts("Error!");
        return 0;
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    head=new node();
    node *tail1=new node(a[1]),*p;
    push(tail1);
    tail1->nxt=new node();
    tail1->pre=head;
    head->nxt=tail1;
    for(int i=2;i<=n;++i)//一开始把链表中的所有元素放进去
    {
        p=Insert(tail1,a[i]);
        tail1=p;
        push(p);
    }
    head=head->nxt;
    tail1->nxt=head;
    head->pre=tail1;
    long long ans=0;
    for(int i=1;i<=m;++i)
    {
        p=heap[1];
        while(p->del)
        {
            pop();
            p=heap[1];
        }
        pop();
        ans+=p->key;
        p->key=p->pre->key+p->nxt->key-p->key;//更新价值并把两边的元素删掉
        Delete(p->pre);
        Delete(p->nxt);
        push(p);
    }
    printf("%lld\n",ans);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */