Identical Day

题目大意

给定一个长度为 \(n\) 的 \(01\) 串，对于每段长度为 \(l\) 的连续的 \(1\) ，其权值为 \(\frac{l\times(l+1)}{2}\) ，对于给出的 \(01\) 串显然可得其权值和。现在你能够将该串中任意的 \(1\) 改为 \(0\) ，问最少改多少次你能使得新串的权值和不超过 \(k\) 。

分析

首先，对于此题，需要知道，对于一个连续 \(1\) 串，在其中更改的时候如何使得效率更高？要到达最好的效果，我们必须要让该串在更改后被分成的几个连续 \(1\) 串含有 \(1\) 的数量尽量平均。

例如：

11111 \\只能更改两个1，如何更改使得效果最好？

10101 \\更改前，权值为15，现在权值为3

11111111111111111 \\只能更改两个1，如何使得更改效果最好？

11101110111101111 \\更改前，权值为105，现在权值为32

注意要尽量平均，如第二个例子，就不能是 \(11101110111011111\) ，这样权值是 \(33\) 。

知道了这一点，接下来我们想想这道题怎么做？

一开始，我们或许会想到使用一个大根堆，将每一段入堆，每次取出最长的一段来平均分，分出来的小段又分别入队。

这么贪心显然是错误的，错在哪里？有可能我们的方案并非最优。

例如：

1111111 \\设其为原串中的一段连续1串

1110111 \\第一次更改

1010111 \\按照我们上述的贪心方案第二次更改会变成这样

1011011 \\实际上更改两个最优应该是这样

那应该怎么办？

保留最开始的大根堆思路，我们可以将一个 \(01\) 串内的每个连续 \(1\) 串单独包装，计算其砍一刀的贡献，砍两刀的贡献（注意砍两刀的贡献是相对于已经砍了一刀的权值）。我们可以重载大根堆运算为贡献大的优先，这样，我们一刀一刀砍，肯定是最优的。

这么做的好处是：

1111111 \\设其为原串中的一段连续1串

1110111 \\第一次更改

1011011 \\若我们发现该段还需要二次更改我们不会管第一次更改，直接在最开始的基础上更改两次，得到最优方案

CODE

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

inline int read()

{

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9') { if(ch=='-') w*=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();

	return s*w;

}

struct node{

	int l; //该段长度

	int v; //当前阶段改变数

	int nex; //至下一阶段变化量

	int val;

	bool operator < (const node &x)const{ //重载运算符

		if(nex<x.nex) return 1;

		return 0;

	}

};

int n,k,ans;

int unhappy; //储存目前的不开心值

int a[N];

priority_queue<node> q;

inline void solve()

{

	while(unhappy>k){

		node now=q.top(),add;

		q.pop(); //出堆

		ans+=1; //更新答案

		unhappy-=now.nex; //更新不快乐值

		int ad=(now.l-now.v-1)/(now.v+2),lv=(now.l-now.v-1)%(now.v+2),temp=0;

		for(int i=1;i<=lv;i++) temp=temp+(ad+1)*(ad+2)/2;

		for(int i=1;i<=now.v+2-lv;i++) temp=temp+ad*(ad+1)/2;

		add.val=temp;

		add.nex=now.val-temp;

		add.l=now.l;

		add.v=now.v+1;

		q.push(add);

	}

}

int main()

{

	n=read(),k=read();

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

		char x=getchar();

		a[i]=x-'0';

	}

	int now=0;

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

		if(a[i]) now++;

		else if(now){

			int temp=now*(now+1)/2; //记录该段在不改变情况下对不开心值的贡献

			int l1=(now-1)/2,l2=(now-1)-l1; //最佳的两段

			unhappy+=temp;

			node add; //处理入堆元素

			add.l=now,now=0;

			add.v=1;

			add.nex=temp-(l1*(l1+1)+l2*(l2+1))/2; //改变一次对答案的最大贡献

			add.val=(l1*(l1+1)+l2*(l2+1))/2;

			q.push(add); //入大根堆

		}

	}

	solve();

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

	return 0;

}

巴特西

I-Identical Day[题解]

Identical Day

题目大意

分析

CODE

最新文章

热门文章