【bzoj2151】种树

            

题面

传送门
传送门2

题解

如果没有相邻限制的话,我们开一个大根堆每一次取最大的就行了,但是如果存在限制,我们就加入一个后悔操作,来做调整贪心。
首先如果我们选择了一个点i,那么其相邻的点i−1,i+1,都不能选了,所以我们删除这两个点,因为i与它们两个是互斥的。
所以我们加入后悔操作的时候,是用两者之和减去a[i],即我们每选择一个点,我们就加入一个新节点 node(i,a[i+1]+a[i−1]−a[i]),这样就可以做到满足限制条件下的调整了,另外就是维护位置,可以链表直接 O(1)做,或者set维护一下也可。

1、链表写法
#include
#include
using namespace std;
const int maxn = 200005;

struct node{
    int id, val;
    node(int id, int val):id(id),val(val){}
    bool operator < (const node &b)const{return valq;

int vis[maxn], pre[maxn], nxt[maxn];
void change(int x){
    vis[x] = 1;  //vis[i]==1,不在链表里的点。
    nxt[pre[x]] = nxt[x];
    pre[nxt[x]] = pre[x];
    pre[x] = 0; nxt[x] = 0;
}

int main(){
    int n, m, a[maxn];
    cin>>n>>m;
    if(n<2*m){cout<<"Error!\n"; return 0;}
    for(int i = 1; i <= n; i++){ cin>>a[i]; q.push(node(i,a[i])); }
    for(int i = 2; i <= n; i++)pre[i] = i-1; pre[1]=n;
    for(int i = 1; i < n; i++)nxt[i] = i+1; nxt[n]=1;

    long long ans = 0;
    for(int i = 1; i <= m; i++){
        while(vis[q.top().id])q.pop();
        node t = q.top();  q.pop();
        ans += t.val;

        int l = pre[t.id], r = nxt[t.id];
        change(l);  change(r);

        a[t.id] = a[l]+a[r]-a[t.id];
        q.push(node(t.id,a[t.id]));//反悔节点
    }
    cout<'\n';
    return 0;
}
2、STL写法
#include
#include
#include
using namespace std;
const int maxn = 200005;

int n, m, a[maxn];
struct node{
    int id, val;
    node(int id, int val):id(id),val(val){}
    bool operator < (const node &b)const{return valstruct data{
    int id, val;
    data(int id, int val):id(id),val(val){}
    bool operator < (const data &b)const{return idq;
sets;
set::iterator pre,nxt;

int main(){
    cin>>n>>m;
    if(n<2*m){cout<<"Error!\n";return 0;}
    for(int i = 1; i <= n; i++){
        cin>>a[i];  q.push(node(i,a[i]));
        s.insert(data(i,a[i]));
    }

    long long ans = 0;
    for(int i = 1; i <= m; i++){
        node t = q.top();  q.pop();
        while(!s.empty() && s.find(data(t.id,t.val))==s.end())
            { t = q.top();  q.pop();}

        ans += t.val;
        if(i == m)break;
        data now = data(t.id,t.val);
        nxt = s.upper_bound(now);
        pre = s.lower_bound(now);
        if(nxt == s.end())nxt = s.begin();
        if(pre == s.begin())pre = --s.end();
        else --pre;

        data to = data(t.id,pre->val+nxt->val-t.val);
        s.erase(s.find(now));
        s.erase(pre);
        s.erase(nxt);
        s.insert(to);

        q.push(node(to.id,to.val));
    }
    cout<"\n";
    return 0;
}
3、最后

垃圾样例怎么改都是对的。

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像