UVa 2678 - Subsequence
传送门
题意
求连续的序列中最少个相加大于等于sum的个数。
思路
s[j] - s[i] >= sum
s[i] <= s[j] - sum.
要使i最大。
这时候可以用lower_bound,直接找i,对于每个j。
代码
#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x) & (-x))
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
int num[MAXN];
int main()
{
//freopen("input.txt", "r", stdin);
int n, s, i, j;
while (~scanf("%d%d", &n, &s))
{
int ans = INF;
for (i = 1; i <= n; i++)
{
scanf("%d", #[i]);
num[i] += num[i - 1];
}
for (i = 1; i <= n; i++)
{
int k = lower_bound(num, num + n, num[i] - s) - num;
if (k > 0)
ans = min(ans, i - k + 1);
}
printf("%d\n", ans == INF ? 0 : ans);
}
return 0;
}