poj3061 poj3320 poj2566尺取法基础(一)

时间:2022-10-13 12:27:00

poj3061 给定一个序列找出最短的子序列长度,使得其和大于等于S

那么只要用两个下标,区间和小于S时右端点向右移动,区间和大于S时左端点向右移动,在这个过程中更新Min

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 100005
#define LL long long
#define INF 0x3f3f3f3f using namespace std;
LL a[];
int n, t, ans = INF;
LL sum, s; int main()
{
scanf("%d", &t);
while (t--){
scanf("%d %I64d", &n, &s);
for (int i = ; i < n; i++) scanf("%I64d", a+i);
int st = , en = ;
ans = INF; sum = ;
while (){
while (en<n && sum<s) sum += a[en++];
if (sum < s) break;
ans = min(ans, en-st);
sum -= a[st++];
}
if (ans == INF) ans = ;
printf("%d\n", ans);
}
return ;
}

poj3320给一本书有P页,每页都有一个知识点,求最少的连续页数覆盖所有知识点

如果一个区间的子区间满足条件,那么右端点固定,左端点推进

反之左端点固定 ,右端点推进么。需要用map进行映射,set求总共有多少知识点

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define MAX 1000010
#define LL long long
#define INF 0x3f3f3f3f using namespace std;
int a[MAX];
map <int, int> cnt;
set <int> t;
int p, ans = INF, st, en, sum; int main()
{
scanf("%d", &p);
for (int i = ; i < p; i++) scanf("%d", a+i), t.insert(a[i]);
int num = t.size();
while (){
while (en<p && sum<num)
if (cnt[a[en++]]++ == ) sum++;
if (sum < num) break;
ans = min(ans, en-st);
if (--cnt[a[st++]] == ) sum--;
}
printf("%d\n", ans);
return ;
}

poj2566 给定一个数组和值t,求一个子区间使得其和的绝对值与t的差值最小

有正有负,不能保证单调性,无法单点拓展边界,预处理出所有的前缀和,升序排列

然后尺取法求出两个端点,使区间和的绝对值最逼近t

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
#define LL long long
#define MAX 100010
using namespace std; typedef pair<LL, int> p;
LL a[MAX], t, ans, tmp, b;
int n, k, l, u, st, en;
p sum[MAX]; LL myabs(LL x)
{
return x>=? x:-x;
} int main()
{
while (scanf("%d %d", &n, &k), n+k){
sum[] = p(, );
for (int i = ; i <= n; i++){
scanf("%I64d", a+i);
sum[i] = p(sum[i-].first+a[i], i);
}
sort(sum, sum++n);
while (k--){
scanf("%I64d", &t);
tmp = INF; st = , en = ;
while(en <= n){
b = sum[en].first-sum[st].first;
if(myabs(t-b) < tmp){
tmp = myabs(t-b);
ans = b;
l = sum[st].second; u = sum[en].second;
}
if(b > t) st++;
else if(b < t) en++;
else break;
if(st == en) en++;
}
if (u < l) swap(u, l);
printf("%I64d %d %d\n", ans, l+, u);
}
}
return ;
}