自动搬运

查看原文

来自洛谷，原作者为

	Perfound 死在了起跑线，死人一生平安

搬运于2025-08-24 22:33:41，当前版本为作者最后更新于2021-09-12 10:13:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7855 「EZEC-9」 暂颓恒卷 题解

为防棕名先发个声明：和 wyy332623 的 3 个代码雷同是因为我一天内交的次数满了,就把代码给他交.

---

思路

---

这题最重要的一点是要知道 1-3 之间（无 2 或 1）可全部变卷。

方便起见，把每个 1-2（之间无 2 或 1）叫做一个区间。

要求最大值，那就先把所有输入的区间内 1-3（离 2 最近的）的距离（包括 2 个端点）之和记作 $res$。

那这 1-3（离 2 最近的）之间的3就没用了，数量记作 $us3$（不包括 2 个端点）。

要移动 3（离 2 最近的）当然要移到那个 2（本区间）边上，区间 i 的移动所加的值记为 $add_ i$。

但这通过率不到 2% 的 大水题 肯定会有像 1-2（无 1 或 2）之间只有 4 的 比较水的 数据，把它定义为 水区间。

那怎么办呢？

肯定先用 $us3$ 因为它可以进行 人见人爱花见花开的白嫖，把它放到 水区间 的 2 边上。

把 水区间 i 内 4 的个数记为 $empty_i$。

那 $res=res+empty_{headempty}$。

$us3=us3-1$（白嫖次数减一）//哭

那有 更水的 数据连 3 都不够（$us3<tailempty-headempty+1$）就 拆东墙补西墙，把区间 i 拆下要减的 1-3 （离 2 最近的）的距离（包括 1 个端点）记为 $wipe_i$（加到 水区间 的 2 边上）

即 $res=res+empty_{headempty}-wipe_{headwipe}$

（$empty_{headempty}-wipe_{headwipe}<0$ 时退出）因为这样 $res$ 会倒减且这是最后方案（即 白嫖失败）

排序：

$add$ 从大到小。

$empty$ 从大到小。

$wipe$ 从小到大。

（$add_{headadd} \geq empty_{headempty}$ 时）先用 $add$。

否则用 $us3$（因为 可以白嫖）最后用 $wipe$，即 有代价的白嫖（$us3$ 没了所以可以用）。

$add_i$ 用了 $wipe_i$ 就用不了了（反过来也一样）用 set 即可解决这个问题。

为使 $add$ 和 $wipe$ 一一对应，$add_k=0$ 时也应算入。

记得把 $wipe$ 生成的 $empty$ 重新加入。

---

代码

---

#include<bits/stdc++.h>
using namespace std;
int add[2000010],wipe[2000010];
struct ad{
	int v,p;
	friend bool operator <(ad x,ad y){
		return x.v==y.v?x.p>y.p:x.v>y.v; 
	}
};
struct wp{
	int v,p;
	friend bool operator <(wp x,wp y){
		return x.v==y.v?x.p<y.p:x.v<y.v; 
	}
};
struct ep{
	int v;
	friend bool operator <(ep x,ep y){
		return x.v>y.v; 
	}
};
set<ad>s1;set<wp>s2;
multiset<ep>s3;
int empty[2000010],is[2000010];
bool cme(int a,int b){return a>b;}
int hw,he,ha;
int ta=-1,tw=-1,te=-1;
int f,b13,b3,b1,b2;
int res,us3;
void usa(){
	auto it=s1.begin();
    s2.erase((wp){wipe[(*it).p],(*it).p});
    res+=(*it).v,s1.erase(it);
}
void usw(){
	auto it=s2.begin();
	s1.erase((ad){add[(*it).p],(*it).p});
    res+=(*s3.begin()).v-(*it).v;
	s3.erase(s3.begin());
	s3.insert((ep){is[(*it).p]});
	s2.erase(it);
}
int main(){
    int k,c,a;
    scanf("%d%d",&k,&c);
    for(int i=1;i<=k;i++){
        scanf("%d",&a);
        if(a==1){
            if(b13>0)wipe[++tw]=i-b3,is[tw]=i-b2-1;
            if(b13<=0&&i!=1)empty[++te]=i+b13-1;
            f=min(f+1,2),us3+=(f==2);
            if(b13>=0)res+=i-b13;
            else res++;
            b13=b1=i,f=0;
        }else if(a==2){
            if(b13!=b1)wipe[++tw]=b13-b1,is[tw]=i-b1-1;
            if(f==0&&i!=1)empty[++te]=i-b13-1;
            if(f>0)add[++ta]=i-b13-1;b13=-i,b2=i,f=0;
        }else if(a==3){
            if(b13>0)res+=i-b13,f=min(f+1,2),us3+=(f==2);//去掉二个端点 f 就这样搞 
            else add[++ta]=i+b13-1,b3=i,res++;b13=i;
        }
    }
    for(int i=0;i<=ta;i++)s1.insert((ad){add[i],i});
    for(int i=0;i<=tw;i++)s2.insert((wp){wipe[i],i});
    for(int i=0;i<=te;i++)s3.insert((ep){empty[i]});
    for(int i=0;i<c;i++){
        if(s3.size()){
            if(s1.size()){
                if((*s1.begin()).v>=(*s3.begin()).v)usa();
                else if((us3--)>0)res+=(*s3.begin()).v,s3.erase(s3.begin());
                else if(!s2.size())usa();
                else if((*s1.begin()).v>=(*s3.begin()).v-(*s2.begin()).v)usa();
                else if((*s3.begin()).v-(*s2.begin()).v>0)usw();
                else break;
            }else if((us3--)>0)res+=(*s3.begin()).v,s3.erase(s3.begin());
            else if(!s2.size())break;
            else if((*s3.begin()).v-(*s2.begin()).v>0)usw();
            else break;
        }else if(s1.size())usa();
        else break;
    }
    cout<<res;
    return 0;
}

---

总结

---

洛谷月赛真是越来越毒瘤了

都开始传播白嫖主义了