HDU 3717 Rescue（二分+技巧性模拟）【详解】

电玩女神 2022-06-09 08:26 130阅读 0赞

The princess is trapped in a magic place. In this place, there are N magic stones. In order to rescue the princess, you should destroy all the stones. The N stones are in a straight line. We number them as s1, s2, ... sn from left to right. Each stone has a magic strength m 1, m 2, ... m n. You have a powerful skill that can do some damage to the stones. To release the skill, you should stand to the right of some stone (s i). Then you throw a power ball towards left. Initially, this ball has a power of p. When it hits a stone, it will do some damage to the stone and its power will be decreased, and the ball will continue to fly left to the next stone if its power is still positive. Formally, if you stand to the right of s i and the power ball's initial power is p, then the ball will do Max(0, p - (i - j) \* (i - j)) damage to sj, for each j <= i. So from this formula, we can see that the damage to stone sj is only determined by the initial power of the ball and the number of stones between s i and s j. A stone is destroyed if the damage you do is larger than its magic strength. Note that even if a stone is destroyed, it will not disappear; your magic ball will do damage to it and the power will be decreased by that stone. You are not strong enough so that you can release at most k magic balls. It will cost a lot of energy if the power of the magic ball is too high. So what is the minimum value of p with which you can destroy all the magic stones, with no more than k magic balls? You can choose where to release each magic ball as your will, and the power of the ball must be a positive integer.

Input

The first line is the number of cases T (T ≤ 100). For each case, the first line gives two integers n, k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 100000). The second line are n integers, giving m 1, m 2, ... m n (1 ≤ m ≤ 10 9).

Output

Print minimum possible p in a line.

Sample Input

2
    1 1
    1
    3 1
    1 4 5

Sample Output

2
    6

题解：

题意：

有一排有魔法值的石头，你可以从任意一个石头的右边开始从右向左放一个冲击波，这个冲击波对从右到左会造成衰减的伤害，当造成的累积伤害大于石头的魔法值这个石头就给被毁了，你n个石头，给一个次数k，问你该冲击波的能量为多少才可以把这些球按照规定次数完全消灭

思路：

这题在两次比赛中都出现了。。第一次比赛，读错题意了。。比完赛补题的时候疯狂wa，然后第二次比赛惊奇的发现还居然是上一场比赛的题。。然后就冷静下来读懂了题意。。然后接下来就是疯狂的TLE了，我也用了二分去找。。。无奈无论怎么优化都还是TLE，错了8次后无奈就去找博客了。。。发现博客模拟得很巧妙。。我为什么那么弱

我就说明一下那人的思路。。。我也是看了好久才看懂的

首先我们用二分枚举所有的p，看要使用的次数和给出规定次数k的关系来找，那么这题的难点就在给出能量p，如何去模拟获得所需的次数ans

我们从右到左枚举每一个石头的位置，保存之前所有冲击波对当前石头的能量损失和，对当前石头有影响的能量波的个数，那么每一个石头所需要的冲击波个数就是：

（当前石头的魔法值-（对当前石头有影响的冲击波个数\*能量p-之前所有冲击波对当前能量的损失和））/p+1，这样就可以用o（n）的方法写出来这题了。。。qaq我的方法一直TLE

下面的代码基本就是照着博客打的。。只是加上了我的注释，因为我根本想不到这种模拟方法

希望我的注释能帮助你们理解这题。。因为我真的看了很久才懂

原博客：[http://www.acmerblog.com/hdu-3717-rescue-6697.html][http_www.acmerblog.com_hdu-3717-rescue-6697.html]

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    ll n,k;
    ll a[50005];//存石头的能量值
    ll cent[50005];//存在第i个位置放了几个冲击波
    bool find(ll x)
    {
        ll sum_2=0,sum_1=0,sum=0,ans=0;//sum2为前面的冲击波到当前石头的能量损失和，sum1为一个公式推出来的中间量用于更新sum2
        int j=n-1;//sum为前面对该石头有影响的冲击波的个数，ans存要用的冲击波数目，j为冲击波放的位置，i为当前小球标号
        for(int i=n-1;i>=0;i--)//我说一下这个公式，就是：之前的能量损失数=冲击波数目*（当前冲击波对当前位置的能量损失）注意能量损失是一个平方公式
        {//这里用了三个变量储存平方公式的三个数值就是  冲击波数目（冲击波位置-当前位置）^2拆开来了，而sum1就是那个中间量
            if(j>i)
            {
                while((j-i)*(j-i)>=x)//处理当前冲击波的影响范围
                {
                    sum_2-=cent[j]*(j-i-1)*(j-i-1);//公式推出的三个量
                    sum_1-=cent[j]*(j-i-1);//为什么是减看后面可以看明白，因为后面是叠加
                    sum-=cent[j];
                    j--;
                }
            }
            sum_2+=2*sum_1+sum;//把公式整合算出能量损失和
            sum_1+=sum;//同样中间变量也要更新，因为sum变了
            ll y=a[i]-sum*x+sum_2;
            if(y<0)cent[i]=0;//如果之前的冲击波已经轰没了该位置的石头
            else cent[i]=y/x+1;//否则就用代码上面说的公式计算需要多少冲击波
            sum+=cent[i];//更新冲击波数目，注意这里是叠加了，所以上面才能减去来算出当前冲击波的数目
            ans+=cent[i];//累加结果
        }
        return ans<=k;
    }
    int main()
    {
        ll l,r,mid;
        int test,i;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%lld%lld",&n,&k);
            for(i=0;i<n;i++)
            {
                scanf("%lld",&a[i]);
                cent[i]=0;
            }
            l=1,r=1e10;
            while(l<r)//二分答案
            {
                mid=(l+r)/2;
                if(find(mid))
                {
                    r=mid;
                }
                else
                    l=mid+1;
            }
            printf("%lld\n",l);
        }
        return 0;
    }

[http_www.acmerblog.com_hdu-3717-rescue-6697.html]: http://www.acmerblog.com/hdu-3717-rescue-6697.html