[原创]华中农业大学第五届程序设计大赛 E One Stroke [枚举]【思维】

2017-05-26 21:36:14 Tabris_ 阅读数：461

博客爬取于2020-06-14 22:40:34
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72773799

题目链接:http://acm.hzau.edu.cn/problem.php?id=1203
——————————————————————————————————————
1203: One Stroke
Time Limit: 2 Sec Memory Limit: 1280 MB
Submit: 274 Solved: 58
[Submit][Status][Web Board]
Description
There is a complete binary tree which includes n nodes. Each node on the tree has a weight w, each edge on the tree is directed from the parent node to the child node. Give you a pen, draw from the any node along the directed edge at one stroke. It is required that the sum of those drawn nodes’ s weight is no more than k. How many node can be drawn at most in one stroke?

Input
The first line input an positive integer T(1<=T<=10)indicates the number of test cases. Next, each case occupies two lines. The first line input two positive integers n(1<=n<=10^6) and k,(1<=k<=10^9)

The second line input n integers w(1<=w <=10^3), indicate the weight of nodes from the first level of the tree and from left to right.

Output
For each test cases, output one line with the most number of nodes can be drawn in one stroke. If any node likes this doesn’t exists, output -1.

Sample Input
1
5 6
2 3 4 1 7
Sample Output
3

——————————————————————————————————————————

题目大意：
就是给你一棵树，每个树上有一个权值，让你找一条最长的从上向下的链，使其权值和不大于k，问你最长的长度是多少。

解题思路：

限制了链式从上到下的，
所以我们可以枚举每个节点所在的链，然后找最远的权值和不到k的点，就是到这个节点最长的长度，

找的时候用二分就好了，当时脑抽写了个BIT，其实发现数组就好了啊，。。

枚举节点在dfs遍历树的过程创建链就好了，

总复杂度O(nlog⁡n)O(n\log n)

注:代码是O(nlog⁡2n)O(n\log^2 n) 把BIT换成普通数组就好了.

附本题代码
———————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 2e6+7;
//const int INF = (~(1<<31));

int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9') ch = getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch = getchar();}
    return x;
}
/*******************************************/
int n,k,mx;

int w[N];

LL sum[N];
# define lowbit(x) (x&-x)
void update(int i,int v){for(;i<=n;i+=lowbit(i))sum[i]+=v;}
LL getSum(int i){LL ans=0;for(;i;i-=lowbit(i))ans+=sum[i];return ans;}

void display(int m){
    for(int i=1;i<=m;i++)  printf("%d ",getSum(i)-getSum(i-1)); puts("");
}

void solve(int m){
//    display(m);
    int l=1,r=m,ans=-1,mid;
    while(l<=r){
        mid = r+l >> 1;
        if(getSum(m)-getSum(mid-1)<=k) ans = mid,r=mid-1;
        else l=mid+1;
    }
    if(ans!=-1)   mx = (mx>(m-ans+1))?mx:(m-ans+1);
//    printf("---- %d %d  %d \n",ans,m,mx);

}

void dfs(int rt,int dep){
    if(rt>n) return;
    update(dep,w[rt]);
    if(w[rt]<=k)
    solve(dep);
    dfs(rt<<1  ,dep+1);
    dfs(rt<<1|1,dep+1);
    update(dep,-w[rt]);
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)      w[i]=read();
        mx = -1;dfs(1,1);
        printf("%d\n",mx);
    }
    return 0;
}