-1

给你 n 棵树，它们的高度在一个数组中。并且给您一个值 k 个单位，即您需要收集的木材量。您可以拥有任意高度的斧头，但在选择时只能使用 1 把斧头。

告诉您应该使用的最佳斧头高度以及您将砍伐哪些树木，以便将浪费降至最低。

如果你用高度 X 的斧头砍一棵高度为 H 的树。如果 H>X 你得到 HX 木材，否则为 0 木材

我尝试了这个问题，但除了蛮力之外我无法思考，这是非常糟糕的复杂性。

更新以下查询：- 如果 ax 高度为 0，则不必浪费 0 表示树高为 2,4，k 为 5。我希望这使查询清楚。

在上述情况下，斧头的高度为 0，我需要砍伐 2 棵树才能获得 5 个单位的木材。浪费将是 1 个单位，我们必须尽量减少，这里是最小的

不需要其他参数，例如力或其他任何参数

4

3 回答 3

0

好像是spoj的eko问题...

1）对树木的高度进行排序。2）减去a[i]（较大的高度）-a[j]（较小的高度树）乘以考虑到尚未被切割的总树...

有关如何工作的更多详细信息，请查看代码

    #define gu getchar();
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
    inline int scan()
    {
        int n=0;
        char ch=gu;
        while(ch<48){ch=gu;}
        while(ch>47){n=(n<<3)+(n<<1)+ch-'0';ch=gu;}
        return n;
    }
bool dec(ll i,ll j)
{
    return (i>j);
}
ll a[1000000]={0};
int main()
{
    int n,i;
    ll l,m;
    scanf("%d %lld",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%lld",a+i);
    sort(a,a+n,greater<ll>());
    //for(int i=0;i<n;i++)
      //  printf("%lld ",a[i]);
    ll k=a[0];
    for(i=1;i<n;i++)
    {
        //printf("*%lld ",m);
        if(a[i]==k)
            continue;
        if((m-((i)*(k-a[i])))<=0)
        {
            if((m-((i)*(k-a[i])))==0)
            {printf("%d\n",a[i]);break;}
            else
            {
                ll z=(ll)(m/(i+1));
                m=m-z*(i);
                if(m==0)
                {printf("%lld\n",k-z);break;}
                if(m-(i+1)<0)
                {printf("%lld\n",k-z-1);break;}
            }
            printf("%lld ",m);
        }
        m=m-((i)*(k-a[i]));
        k=a[i];
    }
    return 0;
}
于 2015-04-11T13:55:15.840 回答
0

[编辑 12/9/2013：最后一句中的固定公式！]

始终可以选择一个斧头高度，以便砍伐高于此高度的所有树木将导致零浪费。

要看到这一点，只需按高度降序对树进行排序，并考虑将斧头高度从最高树的顶部逐渐向下移动。假设最高的树的高度为 h。注意函数

f(x) = total amount of wood cut by using an axe of height h - x to
       chop all trees of at least this height

当 x = 0 时从 0 开始，并且是 x 的递增分段线性函数，没有间断。每当 x 增加超过一棵或多棵树刚刚开始变得可砍伐的点时，f(x) 的变化率就会增加，但这不会引起问题。因此，对于任何所需的木材 y 水平，只需（从概念上）将高度为 y 的水平线与图形 f(x) 相交，然后从该点放下一条垂直线到 x 轴以找到它的值。（如何在我作为练习留下的程序中实际执行此操作，但这里有一个提示：考虑按高度递减顺序查找相邻 x 值 x1、x2 的对，使得在 h - x1 处砍伐产生的木材太少，并且h - x2 产生太多。）

于 2013-08-05T12:54:45.147 回答
0

子集 sum是一个 NP 完全问题，可简化为为给定轴高选择最佳树集的问题。你的那部分问题是 NP 难的，并且最著名的算法具有指数复杂性。

于 2013-08-05T10:17:25.150 回答