今天听说了一个新名词 “尺取法”,做几个简单题刷刷成就感
尺取法
用两个’指针’表示区间[l,r]的左右端点，然后根据条件将左/右端点不断前移，
并更新满足条件的结果，直到右端点走到末尾为止
整个过程分为4步：
1.初始化左右端点
2.不断扩大右端点，直到满足条件
3.如果第二步中无法满足条件，则终止，否则更新结果
4.将左端点扩大1，然后回到第二步
重复上述步骤，直到将右端点走完整个区间为止
尺取法适合连续区间的问题，用尺取法来优化，使复杂度降为了O(n)。
POJ 3601 Subsequence
链接
Subsequence
题意
给定一个长度为N的序列和一个整数S，
求满足区间和大于等于S的最小区间长度
若找不到输出”0”
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<stdio.h>
#define min(a,b) a<b?a:b
const int N=100000;
int a[N+10];
int main()
{
int T,n,s;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int i=1,j=1,sum=0,ans=N+1;
while(i<=n&&j<=n){
sum+=a[j];
if(sum>=s){
ans=min(ans,j-i+1);
sum-=a[i++];
while(i<=j&&sum>=s)
sum-=a[i++];
if(i<j)
ans=min(ans,j-(i-1)+1);
}
j++;
}
if(ans==N+1)
ans=0;
printf("%d\n",ans);
}
return 0;
}
|
POJ 3320 Jessica’s Reading Problem
链接
Jessica’s Reading Problem
题意
给定P个ideas的ID，求包含所有不同ID的最小区间的长度
分析
ID的值太大，不能开数组标记
可以用hash来编号，我用的map
第一个元素为ID的值，第二个为这个ID的个数
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<stdio.h>
#include<map>
const int N=1000000;
using namespace std;
int a[N+10];
map<int,int> m;
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
m.clear();
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(m[a[i]]==0){
sum++;
m[a[i]]=1;
}
}
m.clear();
int i=1,j=1,ans=N,cnt=0;
while(i<=n&&j<=n){
if(m[a[j]]==0)
cnt++;
m[a[j]]++;
if(cnt==sum){
ans=min(ans,j-i+1);
while(i<=j&&cnt==sum){
m[a[i]]--;
if(m[a[i]]==0)
cnt--;
i++;
}
if(i<=j)
ans=min(ans,j-(i-1)+1);
}
j++;
}
printf("%d\n",ans);
}
return 0;
}
|