首页 > ACM题库 > HDU-杭电 > HDU 3717-Rescue-分治-[解题报告]HOJ
2015
02-21

HDU 3717-Rescue-分治-[解题报告]HOJ

Rescue

问题描述 :

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 m1, m2, … mn. 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 (si). 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 si 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 si and sj. 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.

输入:

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 m1, m2, … mn (1 ≤ m ≤ 109).

输出:

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 m1, m2, … mn (1 ≤ m ≤ 109).

样例输入:

2
1 1
1
3 1
1 4 5

样例输出:

2
6

思路:二分答案,然后模拟消灭石头的过程;

如果单纯的暴力模拟的话,肯定会T的;

所以要用到一定的技巧来维护;

在网上看到大神们用O(n)的复杂度来优化,真心orz;

原理是这样的:用一个变量sum_2存前面所有的对当前石头造成影响的冲击波的损失的能量和;

所以对于当前的石头所需要的新的冲击波的数量为:(当前石头的能量值-前面有影响的冲击波数*能量x+sum_2)/能量x+1;

然后就是维护sum_2了!

维护sum_2要利用这个公式:(x+1)^2=x^2+2*x+1;

 #include<iostream>
 #define maxn 50005
 #define ll long long
 using namespace std;
 ll cnt[maxn];
 ll num[maxn];
 int n,k,t;
 bool check(ll x)
 {
     ll sum_2=0,sum_1=0,sum=0,ans=0;
     int j=n-1;
     for(int i=n-1;i>=0;i--)
     {
         if(j>i)
         {
             while((j-i)*(j-i)>=x)
             {
                 sum_2-=cnt[j]*(j-i-1)*(j-i-1);
                 sum_1-=cnt[j]*(j-i-1);
                 sum-=cnt[j];
                 j--;
             }
         }
         sum_2+=2*sum_1+sum;
         sum_1+=sum;
         ll y=num[i]-sum*x+sum_2;
         if(y<0)cnt[i]=0;
         else cnt[i]=y/x+1;
         sum+=cnt[i];
         ans+=cnt[i];
     }
     return ans<=k;
 }
 
 
 int main()
 {
     cin>>t;
     while(t--)
     {
         cin>>n>>k;
         for(int i=0;i<n;i++)cin>>num[i];
         ll l=1,r=1e12;
         while(l<r)
         {
             ll mid=(l+r)>>1;
             if(check(mid))r=mid;
             else l=mid+1;
         }
         cout<<l<<endl;
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/yours1103/p/3414737.html


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  4. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)