HDU-6609 Find the answer (权值线段树)

本文主要是介绍HDU-6609 Find the answer (权值线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

 

 

题目：

Given a sequence of n integers called W and an integer m. For each i (1 <= i <= n), you can choose some elements WkWk (1 <= k < i), and change them to zero to make ∑ij=1∑j=1iWjWj<=m. So what's the minimum number of chosen elements to meet the requirements above?.

Input

The first line contains an integer Q --- the number of test cases. 
For each test case: 
The first line contains two integers n and m --- n represents the number of elemens in sequence W and m is as described above. 
The second line contains n integers, which means the sequence W. 

1 <= Q <= 15 
1 <= n <= 2*105105 
1 <= m <= 109109 
For each i, 1 <= WiWi <= m

Output

For each test case, you should output n integers in one line: i-th integer means the minimum num

这篇关于HDU-6609 Find the answer (权值线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---