Poj3061 Subsequence

Problem

Subsequence

Solution

方法一：O(nlogn)

1. 计算前序和
2. 定起点，二分找不小于S的最小的连续区间和

方法二：O(n)

1. 定起点，线性找不小于S的最小的连续区间和，得到一个终点
2. 把起点向右移动一个单位，把终点在原来的基础上递增，线性找不小于S的最小的连
   续区间和。如此反复。

Code

方法一：

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, S;
vector<int> a, presum;

void solve() {

  cin >> N >> S;
  presum.clear();
  a.clear();

  a.reserve(N);
  presum.reserve(N + 1);

  for (int i = 0; i < N; ++i) {
    int tmp;
    cin >> tmp;
    a.push_back(tmp);
  }

  // presum[i] means sum of [0, i) elements
  // j > i, presum[j] - presum[i] means sum of [i, j) elements
  presum.push_back(0);

  for (int i = 0; i < N; ++i) {
    presum.push_back(presum[i] + a[i]);
  }

  if (presum[N] < S) {
    cout << 0 << endl;
    return;
  }

  int ans = N;

  for (int i = 0; presum[N] - presum[i] >= S; ++i) {
    int len = distance(presum.begin() + i,
                       lower_bound(presum.begin() + i,
                                   // here can ALSO be presum + N + 1
                                   presum.end(), presum[i] + S));
    ans = min(ans, len);
  }

  cout << ans << endl;
}

int main(void) {
#ifndef ONLINE_JUDGE
  freopen("3061.txt", "r", stdin);
#endif

  int n;

  cin >> n;

  while (n--) {
    solve();
  }
}

方法二：

C

#include <stdio.h>

int N, S;
int a[100 * 1000 + 10];

void solve() {
  scanf("%d%d", &N, &S);
  for (int i = 0; i < N; ++i) {
    scanf("%d", a + i);
  }
  int i = 0, j = 0, sum = 0, ans = N + 1;
  while (1) {
    while (sum < S && j < N) {
      sum += a[j];
      ++j;
    }
    if (sum < S) {
      break;
    }
    ans = (ans < j - i) ? ans : j - i;
    sum -= a[i];
    ++i;
  }
  if (ans == N + 1) {
    ans = 0;
  }
  printf("%d\n", ans);

  return;
}

int main(void) {
  int n;
  scanf("%d", &n);
  while (n--) {
    solve();
  }
  return 0;
}

Common Lisp

(defvar *N*)
(defvar *S*)
(defvar *a*)
(defvar n)

(defun print-array ()
  (loop for i from 0 to (1- (length *a*)) do
    (format t "~d " (elt *a* i)))
  (format t "~%"))

(defun solve ()
  (let ((sum 0)
        (i 0)
        (j 0)
        (ans (+ 1 *N*)))
    (block while
      (loop
        (do ()
            ((or (>= sum *S*)
                 (>= j *N*)))
          (incf sum (aref *a* j))
          (incf j))
        (if (< sum *S*)
            (return-from while))
        (setf ans (min ans (- j i)))
        (decf sum (aref *a* i))
        (incf i)))
    (if (equal ans (1+ n))
        (setf ans 0))
    (format t "~d~%" ans)))

(with-open-file (*standard-input*
                 "3061.txt"
                 :if-does-not-exist nil)
  (setf n (read))
  (dotimes (i n)
    (setf *N* (read))
    (setf *S* (read))
    (setf *a* (make-array *N*
                                  :element-type 'integer
                                  :fill-pointer 0
                                  :adjustable t))
    (dotimes (j *N*)
      (vector-push-extend (read) *a*))
    (solve)))