Java教程

尺取算法模板及例题

本文主要是介绍尺取算法模板及例题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

例题:http://poj.org/problem?id=3061

 

模板:

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #define ll long long
 5 #define inf 0x3f3f3f3f
 6 using namespace std;
 7 const int N = 100000 + 10;
 8 int a[N];
 9 
10 int main() {
11 
12     int T;
13     cin >> T;
14     while (T--) {
15         int n, s;
16         cin >> n >> s;
17         for (int i = 0; i < n; i++) {
18             cin >> a[i];
19         }
20         int l = 0, r = 0, sum = 0, ans = inf;
21         while (1) {
22             while (sum < s && r < n) {
23                 sum += a[r++];
24             }
25             if (sum < s) break;
26             ans = min(ans, r - l);
27             sum -= a[l++];
28         }
29         if (ans == inf) cout << 0 << "\n";
30         else cout << ans << "\n";
31     }
32 
33     return 0;
34 }

 

这篇关于尺取算法模板及例题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!