Educational Codeforces Round 147 (Rated for Div. 2) (贪心）

原题链接：https://codeforces.com/contest/1821/problem/D

* 题意：从1开始走，走的给定区间的值要k次。且shift按了要松开，代表走了一个区间除了往右的次数，还要多两次按shift的次数， 求最小次数。

* 思路：

1. 先把不可能的情况列出来，就是给出的区间大小小于k时直接输出-1

2. 我的思路是暴力把每个区间大小用 数组c 列出来，再前缀和一下。只要我当前的前缀和大小大于k， 代表这里一定有解，再求在这个前缀和下的最优解，可以知道 ans = 区间个数 * 2 + 走到的最末点， 所以在最末点的情况下，要区间个数将尽可能得小。我用的是优先队列存区间值，多了我就把最小的区间值删掉，这样能保证所用区间的个数最小。

* AC代码：

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 2, 0), b(n + 2, 0), s(n + 2, 0);
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) cin >> b[i];
    int sum = 0;
    vector<int> c;
    c.push_back(0);
    for (int i = 1; i <= n; i ++)
    {
    	c.push_back(b[i] - a[i] + 1);
    	sum += (b[i] - a[i] + 1);
    }
    for (int i = 1; i <= n; i ++)
    {
    	s[i] = c[i] + s[i - 1];
    }
    if (sum < k) {cout << -1 << '\n';return;}
    
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; i ++)
    {
		s[i] = c[i] + s[i - 1];    
    }
    int ans = 1e18, res = 0, cnt = 0, r = 1;
    q.push(c[1]);
	while (r <= n)
	{
		if (s[r] - res >= k && q.size())
		{
			int cot = s[r] - res - k;
			// cout << cot << '\n';
			cot = b[r] - cot + (r - cnt) * 2;

			ans = min(ans, cot);
			cnt ++;
			res += q.top();
			q.pop();
		}
		else 
		{
			r ++;
			if (r > n) break;
			q.push(c[r]);
		}
	}
	cout << ans << '\n';
}