#include <iostream> //nlogn復雜度的寫法 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int moder = 1e9 + 7; const int maxn = 100005;int a[maxn];int main() {int t;cin >> t;while(t--){int n,s;scanf("%d%d",&n,&s);for(int i=1;i <= n;i++)scanf("%d",&a[i]);for(int i=2;i <= n;i++){a[i] = a[i] + a[i-1];}if(a[n] < s) printf("0\n");else{int res = n;for(int i=1;a[n]-a[i] >= s;i++){int t = lower_bound(a+1,a+n+1,s+a[i]) - a; // - a 非 - a - 1res = min(res,t-i);}printf("%d\n",res);}}return 0; } /*2 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5 */

?O(n)復雜度的寫法

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int moder = 1e9 + 7; const int maxn = 100005;int a[maxn];int main() {int t;cin >> t;while(t--){int n,s;scanf("%d%d",&n,&s);for(int i=1;i <= n;i++)scanf("%d",&a[i]);int i=1,j=1;int sum=0;int res = n+1;for(;;){while(i <= n && sum < s){sum += a[i];i++;}if(sum < s) break;res = min(res,i-j);sum = sum - a[j];j++;}if(res > n) res = 0;printf("%d\n",res);}return 0; } /*2 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5 */

——

轉載于:https://www.cnblogs.com/cunyusup/p/8446801.html

總結

以上是生活随笔為你收集整理的尺取法——POJ3061的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。