I、Identical Day from 第二届“联想杯”

贪心的策略有些问题，如果用堆维护最长段对半分显然不会是最优的（尽量均分成3段比中间切一刀加上左1/4切一刀更优）

正确的贪心策略是堆维护把一段均分成x段的变成均分成x+1段可以减少多少权值，每次取最大肯定是最优的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define pii pair<int,int>
#define pll pair<ll,ll>
const double PI = acos(-1);
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 2e5 + 5;
ll mod = 1e9 + 7;


//不应该去贪心对半分，而是去贪心每次取可消除差值最大

ll f(ll x)
{
	return x * (x + 1) / 2;
}

ll cut(ll x, ll n)//把x长的1分成n+1份
{
	if (n == x)
		return 0;
	x -= n;//中间要切n刀，分成n+1份，每份长x/(n+1)
	n++;
	if (x % n == 0)//刚好均分
		return n * f(x / n);
	ll cha = x % n;
	return cha * f(x / n + 1) + (n - cha) * f(x / n);
}

struct node {
	ll a, b, c;
	friend bool operator<(node x, node y)
	{
		return x.a < y.a;
	}
};

priority_queue<node>q;

int main()
{
	fastio;
	ll n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	ll sum = 0;
	ll now = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '0')
		{
			if (sum)
			{
				now += f(sum);
				q.push({ f(sum) - cut(sum,1),1,sum }), sum = 0;
			}
		}
		else
			sum++;
	}
	if (sum)
	{
		now += f(sum);
		q.push({ f(sum) - cut(sum,1),1,sum }), sum = 0;
	}
	ll ans = 0;
	while (now > k && !q.empty())
	{
		ll cha = q.top().a;
		n = q.top().b, sum = q.top().c;
		q.pop();
		//cout << cha << endl;
		ans++;
		now -= cha;
		if (n < sum)
			q.push({ cut(sum, n) - cut(sum, n + 1),  n + 1,sum  });
	}
	cout << ans;
	return 0;
}