UVa 2678 - Subsequence

传送门

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;
}

Powered by Jekyll and Theme by solid