| Time Limit: ?1000MS | ? | Memory Limit: ?65536K |
| Total Submissions: ?8403 | ? | Accepted: ?3264 |
Description
Input
Output
Sample Input
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3
Source
第一種方法:
先求出sum[i],從第1個數到第i個數的區間和,每次固定一個開始查找的起點sum[i], ?然后採用二分查找找到 sum[i] + S 的位置,區間長度即為(末位置-(起始位置-1)),用ans保存過程中區間的最小值。時間復雜度 0(nlogn)
代碼:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=100010;
int num[maxn];
int sum[maxn];
int n,S;
int main()
{
int t;scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&S);
sum[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
sum[i]=sum[i-1]+num[i];
}
if(sum[n]<S)
{
cout<<0<<endl;
continue;
}
int ans=maxn;
for(int s=0;sum[s]+S<=sum[n];s++)//從sum[s+1]開始查找,s是開始查找的數的前一個位置
{
int t=lower_bound(sum+s+1,sum+n+1,sum[s]+S)-(sum+s);//sum+s是從第sum+s+1個地址開始查找的前一個地址,所以找到的地址減去這個地址即為區間長度
ans=min(ans,t);
}
printf("%d\n",ans);
}
return 0;
}
另外一種方法:尺取法
重復地推進區間的開頭和末尾
,來求滿足條件的最小區間的方法稱為尺取法。
主要思想為:當a1, ?a2 ?, a3 滿足和>=S,得到一個區間長度3,那么去掉開頭a1, ? 剩下 a2,a3,推斷是否滿足>=S,假設滿足,那么區間長度更新,假設不滿足。那么尾部向后拓展,推斷a2,a3,a4是否滿足條件。
反復這種操作。
個人對尺取法的理解:
當一個區間滿足條件時。那么去掉區間開頭第一個數,得到新區間。推斷新區間是否滿足條件,假設不
滿足條件。那么區間末尾向后擴展,直到滿足條件為之。這樣就得到了很多滿足條件的區間,再依據題
意要求什么,就能夠在這些區間中進行選擇,比方區間最長,區間最短什么的。
這樣跑一遍下來。時間
復雜度為O(n)。
代碼:
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn=100010;
int num[maxn];
int n,S;
int main()
{
int t;scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&S);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
int sum=0,s=1,e=1;
int ans=n+1;
for(;;)
{
while(e<=n&&sum<S)
sum+=num[e++];
if(sum<S)
break;
ans=min(ans,e-s);
sum-=num[s++];
}
if(ans==n+1)
cout<<0<<endl;
else
cout<<ans<<endl;
}
return 0;
}
另外一種方法求區間長度的方法為 (末位置+1-起始位置)
版權聲明:本文博客原創文章,博客,未經同意,不得轉載。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061
微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元

