你好啊又是我
Dragon33038 · · 题解
诡异贪心做法。
模拟赛 T3，场切了，但是看洛谷标签吓哭了。
首先发现每个位置最多只放一个床垫，所以是一个类似背包的问题。设
发现答案有单调性，不过我不会 check。由于只会给一定会造反的囚犯右侧加上床垫，想到贪心。
一个初步的想法是每次给影响最大（放了床垫会减少造反囚犯数量最大）的囚犯加上床垫并快速更新其他囚犯对应的影响，但这样会有一个问题（
橙色区间表示这个囚犯不加床垫能影响到的范围。我们发现给第一个囚犯加上床垫不能改变答案，因为后面的囚犯也覆盖了后面的位置，后面放床垫的操作会改变当前的影响。我们需要一个方法使得一个囚犯的影响只和覆盖的范围和已经进行的决策有关。
所以考虑正难则反，我们把每个囚犯右都加上床垫，然后依次把影响最小的删除。这样整个序列被床垫分成了一个囚犯和其左侧一部分区域组成的若干个连通块，那么一个连通块的影响即删除其右侧床垫能影响的范围。
当去掉一个床垫时，其的影响就是对应左侧连通块覆盖范围还是
但是对于上图左数第二个连通块，我们发现其覆盖范围并没有那么大，因为其右侧还有一个床垫，所以计算实际影响范围要和下一个连通块的右端点取最小。不难发现每次操作只会从连通块的右侧延申，所以我们要维护连通块最后一个
每次操作就是合并两个连通块，这个时候只有该连通块和其左侧的连通块对应的影响会变化，可以用链表维护每个连通块。
为什么每次取贪心最小的是不劣的？感性理解一下：
初始时因为连通块限制了影响范围，所以每个连通块去掉右侧床垫的影响依次是
然后就做完了，要注意特判右侧是边界
代码留有场上注释和对拍。
#include <bits/stdc++.h>
using namespace std;
#define QwQ return
#define egg 0;
//#define int long long
#define iny unsigned long long
constexpr int maxn=2e6+13;
constexpr int maxm=1e7+27;
constexpr int mod=998244353 ;
constexpr double eps=1e-7;
//constexpr int inf=LONG_LONG_MAX>>2;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void slow_print(__int128 x)
{
if(x<0)
{
putchar('-');
}
if(x>9)
{
slow_print(x/10);
}
putchar(x%10+'0');
}
#define ll long long
int n,D,T;
int t[maxn];//最早覆盖的时间
typedef struct ppp
{
int L,R;//左边右边块编号
int visR;//当前块的右端点
int addR;//被覆盖的右端点
}ppp;//要注意特判右侧是n的情况
ppp link_[maxn];//块的链表
int add[maxn];//当前删除该块的右隔音会增加的囚犯
int head;
int have;
typedef struct qqq
{
int u,add;//状态对应链表的下标 状态对应增加囚犯
bool operator<(const qqq &c)const
{
return add>c.add;
}
}qqq;
int tree[maxn<<2];
int tag[maxn<<2];
void build(int p=1,int l=1,int r=n)
{
tag[p]=0;
if(l==r)
{
tree[p]=(t[l]>T);
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
inline void pushdown(int p)
{
if(tag[p])
{
tree[p<<1]=0;
tag[p<<1]=1;
tree[p<<1|1]=0;
tag[p<<1|1]=1;
tag[p]=0;
}
}
void update(int x,int y,int p=1,int l=1,int r=n)
{
if(x<=l&&r<=y)
{
tree[p]=0;
tag[p]=1;
return ;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid)
{
update(x,y,p<<1,l,mid);
}
if(y>mid)
{
update(x,y,p<<1|1,mid+1,r);
}
tree[p]=tree[p<<1]+tree[p<<1|1];
}
int query(int x,int y,int p=1,int l=1,int r=n)
{
if(x<=l&&r<=y)
{
return tree[p];
}
pushdown(p);
int mid=(l+r)>>1;
int res=0;
if(x<=mid)
{
res+=query(x,y,p<<1,l,mid);
}
if(y>mid)
{
res+=query(x,y,p<<1|1,mid+1,r);
}
return res;
}
void read_()
{
n=read(),D=read(),T=read();
for(int i=1;i<=n;++i)
{
t[i]=read();
}
}
int ans;
void sol()
{
for(int i=1;i<=n;++i)
{
link_[i]={0,0,0,0};
add[i]=0;
}
ans=0;
head=0,have=0;
priority_queue<qqq>q;
for(int i=n;i>=1;--i)
{
if(t[i]<=T)
{
link_[i].visR=i;
link_[i].addR=i;
if(head)
{
link_[i].R=head;
link_[head].L=i;
add[i]=min(head-1,T-t[i]+i)-i;
q.push({i,add[i]});
}
else
{
add[i]=min(n,T-t[i]+i)-i;
q.push({i,add[i]});
}
head=i;
if(i^n)
{
++have;
}
++ans;
}
}
link_[0]={0,0,0,0};
build();
while(!q.empty()&&have>D)
{
int u=q.top().u,_add=q.top().add;
q.pop();
if(add[u]^_add)
{
continue;
}
if(link_[u].visR==n)
{
continue;
}
//cout<<'a'<<endl;
ans+=add[u];
add[u]=-1;
--have;
if(link_[u].R)
{
//cout<<'b'<<endl;
int rs=link_[u].R;
int to=min(link_[rs].visR,T-t[link_[u].addR]+link_[u].addR);
t[to]=min(t[to],t[link_[u].addR]+(to-link_[u].addR));
update(link_[u].addR,to);
add[rs]=-1;
link_[u].visR=link_[rs].visR;
link_[u].addR=max(to,link_[rs].addR);
//cout<<'f'<<endl;
if(link_[rs].R)
{
link_[u].R=link_[rs].R;
link_[link_[rs].R].L=u;
rs=link_[rs].R;
int to2=min(link_[rs].visR,T-t[link_[u].addR]+link_[u].addR);
add[u]=query(link_[u].addR,to2);
q.push({u,add[u]});
}
else
{
link_[u].R=0;
int to2=min(n,T-t[link_[u].addR]+link_[u].addR);
add[u]=query(link_[u].addR,to2);
q.push({u,add[u]});
}
//cout<<'g'<<endl;;
if(link_[u].L)
{
int ls=link_[u].L;
int to2=min(link_[u].visR,T-t[link_[ls].addR]+link_[ls].addR);
//cout<<link_[ls].addR<<' '<<to2<<' '<<t[link_[ls].addR]<<endl;
// if(link_[ls].addR>to2)
// {
// ans=-1;
// return ;
// }
add[ls]=query(link_[ls].addR,to2);
q.push({ls,add[ls]});
}
//cout<<'c'<<endl;
}
else
{
//cout<<'d'<<endl;
int to=min(n,T-t[link_[u].addR]+link_[u].addR);
t[to]=min(t[to],t[link_[u].addR]+(to-link_[u].addR));
update(link_[u].addR,to);//线段树区间赋值(1)
link_[u].visR=n;
link_[u].addR=to;
if(link_[u].L)
{
int ls=link_[u].L;
int to2=min(n,T-t[link_[ls].addR]+link_[ls].addR);
add[ls]=query(link_[ls].addR,to2);//query是线段树返回区间0的数量
q.push({ls,add[ls]});
}
//cout<<'e'<<endl;
}
//cout<<'z'<<endl;
}
}
bool used[maxn];
int ans2;
void check()
{
int now=T+1;
int res=0;
for(int i=1;i<=n;++i)
{
now=min(now+1,t[i]);
if(now<=T)
{
++res;
}
if(used[i])
{
now=T+1;
}
}
ans2=min(ans2,res);
}
void dfs(int u,int sum)
{
if(u==n)
{
if(!sum)
{
check();
}
return ;
}
if(sum)
{
used[u]=1;
dfs(u+1,sum-1);
used[u]=0;
}
dfs(u+1,sum);
}
void sol_small()
{
ans2=n;
dfs(1,D);
}
mt19937_64 rd(random_device{}());
signed main()
{
/*
//首先暴力做法是一个有nd状态的dp，而且算贡献有点复杂，显然过不去
//答案有单调性想到二分答案，但是好像不好check
//2e6 这个数据量很神奇啊
//也许是直接贪心放置？但是因为可行的囚犯也可能提前所以不好得到新状态
//反过来，贪心删除
//给每个人右侧加一个隔音，然后贪心删除影响小的
//这样是合并两个块或者增加连续一段空的
//好像不是很对，好像不知道怎么写
//同时维护当前结果每个末尾的最早时间
//但是增加贡献不连续sos
//由于每个位置只会覆盖一次所以均摊O(n)?
//额我好像可以上线段树
//牛逼呐小样例AC大样例WA我咋调
//sos我还没写Dn^2 dp
//
*/
read_();
sol();
printf("%d\n",ans);
// for(int _=0;_<10000;++_)
// {
// n=rd()%10+2;
// D=rd()%(n-1)+1;
// T=rd()%100+1;
// for(int i=1;i<=n;++i)
// {
// t[i]=rd()%100+1;
// }
// //cout<<'a'<<endl;
// sol();
// //cout<<'b'<<endl;
// sol_small();
// //cout<<'c'<<endl;
// if(ans^ans2)
// {
// printf("%d %d %d\n",n,D,T);
// for(int i=1;i<=n;++i)
// {
// printf("%d ",t[i]);
// }
// printf("\n%d %d\n",ans,ans2);
// QwQ egg
// }
// }
// printf("\nProcess returned 0 (0x0) execution time : 0.022 s\nPress any key to continue.\n");
// string some_string;
// while(cin>>some_string);
/*
//I often die
//I often die
//I often die
//I often die
//I often die
//I often die
//I often die
//I often die
//I always die */
QwQ egg
}