Find the answer

Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

Given a sequence of n integers called W and an integer m. For each i (1 <= i <= n), you can choose some elements W**k (1 <= k < i), and change them to zero to make ∑i**j=1W**j<=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*105

1 <= m <= 109

For each i, 1 <= W**i <= m

Output

For each test case, you should output n integers in one line: i-th integer means the minimum number of chosen elements W**k (1 <= k < i), and change them to zero to make ∑i**j=1W**j<=m.

Sample Input

2

7 15

1 2 3 4 5 6 7

5 100

80 40 40 40 60

Sample Output

0 0 0 0 0 2 3

0 1 1 2 3

题意

自己读题，几句话很难说清楚

转化一下就是将最少的数变成0，并且自己不能选，使\(\sum_{j=1}^{i} \leq m\),输出最小的次数。

题解

贪心一下，取最大的几个。

离散+权值线段树就成。

代码

#include<bits/stdc++.h>

#define int long long

#define DEBUG cerr << "Call out: " << __func__ << "\t" << "Line: " << __LINE__ << "\t :"

using namespace std;

#define MAXN 200010

struct sgt

{

	int val,p;

	int l,r;

} f[MAXN<<2];

int wh[MAXN];

int a[MAXN];

pair <int,int> pt[MAXN];

int n;

int m;

void build(int x,int l,int r)

{

	f[x].l = l;

	f[x].r = r;

	f[x].val = f[x].p = 0;

	if (l == r) return;

	build(x<<1,l,(l+r)>>1);

	build(x<<1|1,((l+r)>>1)+1,r);

}

void add(int x,int pos,int val)

{

	f[x].val += val;

	f[x].p ++;

	if (f[x].l == pos && f[x].r == pos) return;

	if (pos > f[x<<1].r) add(x<<1|1,pos,val);

	else add(x<<1,pos,val);

}

int query(int x,int val)

{

	if (f[x].l == f[x].r)

		if (f[x].val == val) return f[x].p;

		else return 0;

	if (f[x<<1].val >= val) return query(x<<1,val);

	return f[x<<1].p + query(x<<1|1,val - f[x<<1].val);

}

signed main()

{

	int T;

	cin >> T;

	while (T--)

	{

		cin >> n >> m;

		memset(f,0,sizeof(f));

		build(1,1,n);

		for (int i=1; i<=n; i++)

			scanf("%d",a+i),pt[i].first = a[i], pt[i].second = i;

		sort(pt+1,pt+n+1);

		for (int i=1; i<=n; i++)

			wh[pt[i].second] = i;

		int tot = 0;

		for (int i=1; i<=n; i++)

		{

			tot += a[i];

			if (tot <= m) printf("0 ");

			if (tot > m) printf("%d ",i-query(1,m-a[i])-1);

			add(1,wh[i],a[i]);

		}

		puts("");

	}

}

巴特西

2019 Multi-University Training Contest 3 T7 Find the answer

Find the answer

Input

Output

Sample Input

Sample Output

题意

题解

代码

最新文章

热门文章