《算法竞赛入门经典——训练指南》代码

《算法竞赛入门经典——训练指南》代码仓库 例题代码 限于篇幅，书上并没有给出所有例题的代码，这里给出了所有例题的代码，并且改进了书上的一些代码。

// LA2678 Subsequence O（n） version
// Rujia Liu
#include
#include
using namespace std;

const int maxn = 100000 + 10;
int A[maxn] B[maxn];
int main（） {
  int n S;
  while（scanf（“%d%d“ &n &S） == 2 && n） {
    for（int i = 1; i <= n; i++） scanf（“%d“ &A[i]）;
    B[0] = 0;
    for（int i = 1; i <= n; i++） B[i] = B[i-1] + A[i];
    int ans = n+1;
    int i = 1;
    for（int j = 1; j <= n; j++） {
      if（B[i-1] > B[j]-S） continue; // （1）没有满足条件的i，换下一个j
      while（B[i] <= B[j]-S） i++;    // （2）求满足B[i-1]<=B[j]-S的最大i
      ans = min（ans j-i+1）;
    }
    printf（“%d\n“ ans == n+1 ? 0 : ans）;
  }
  return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1259  2013-04-23 15:55  readme.txt

     文件        674  2013-02-28 13:16  ch1\la2678.cpp

     文件        570  2013-02-28 13:16  ch1\la2678_n2.cpp

     文件        564  2013-02-28 13:16  ch1\la2678_n3.cpp

     文件        579  2013-02-28 13:16  ch1\la2678_nlogn.cpp

     文件       1297  2013-02-28 13:16  ch1\la2965.cpp

     文件       1795  2013-02-28 13:16  ch1\la2995.cpp

     文件       1260  2013-02-28 13:16  ch1\la3029.cpp

     文件       1166  2013-02-28 13:12  ch1\la3177.cpp

     文件       1984  2013-03-23 14:37  ch1\la3401.cpp

     文件        981  2013-03-23 14:34  ch1\la3401_make.cpp

     文件        733  2013-02-28 13:16  ch1\la3635.cpp

     文件       1441  2013-02-28 13:16  ch1\la3695.cpp

     文件        436  2013-02-28 13:16  ch1\la3708.cpp

     文件        379  2013-02-28 13:16  ch1\la3882.cpp

     文件       1532  2013-02-28 13:16  ch1\la3902.cpp

     文件       1281  2013-02-28 13:16  ch1\la3905.cpp

     文件       1290  2013-02-28 13:16  ch1\la3905_int.cpp

     文件       1371  2013-02-28 13:16  ch1\la3971.cpp

     文件       1116  2013-02-28 13:16  ch1\la3983.cpp

     文件       1319  2013-02-28 13:16  ch1\la4794.cpp

     文件       1548  2013-02-28 14:00  ch1\readme.txt

     文件        981  2013-02-28 13:16  ch1\uva10635.cpp

     文件       1450  2013-02-28 13:16  ch1\uva10755.cpp

     文件        766  2013-02-28 13:16  ch1\uva10795.cpp

     文件       1615  2013-02-28 13:16  ch1\uva10859.cpp

     文件       1411  2013-02-28 13:16  ch1\uva10881.cpp

     文件        967  2013-02-28 13:16  ch1\uva10891.cpp

     文件        733  2013-02-28 13:16  ch1\uva10891_slow.cpp

     文件        590  2013-02-28 13:16  ch1\uva11078.cpp

............此处省略169个文件信息