poj 2189 / 3061 욕심 (연속 적 인 양우리 찾기 / 연속 적 인 하위 서열 의 합 이 limit 보다 큰 최 단 서열 찾기)

제목: 이미 한 줄 의 양우리 가 두 줄 로 연결 되 어 있 고 중간 은 하나의 울타리 로 나 뉘 어 져 있다.울타리 번호 1 - n 을 매기 면 모두 n - 1 개의 양우리 가 있 습 니 다.m 개의 양 이 있 는 위 치 를 정 합 니 다. 예 를 들 어 한 양 이 x 에 있다 면 그 는 x 와 x + 1 에 둘러싸 인 양우리 에 있다 는 것 을 의미 합 니 다.상수 c 를 하나 더 정 하고 가장 큰 연속 구간 을 구하 여 그 중의 양 총수 가 c 를 초과 하지 않도록 한다.
생각: 욕심 만 부리 면 된다.커서 i 와 j 두 개 를 설정 하여 한 번 훑 어보 세 요.고정 기점 i 가 조건 에 부합 할 수 있 는 가장 긴 구간 을 구 하 는 것 과 같다.

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s))
#define N 1005
int n,m,c;
int s[N];
int main(){
    int i,j,x,res,num;
    scanf("%d %d %d",&m,&n,&c);
    clr(s, 0);
    for(i = 0;i<m;i++){
        scanf("%d",&x);
        s[x]++;
    }
    res = num = 0;
    for(i = j = 1;i<n;i++){
        num -= s[i-1];
        while(num <= c && j<n){
            num += s[j];
            j++;
        }
        res = max(res,j-i-1);
        if(j == n){
            if(num <= c)//      wa   
                res = max(res,j-i);
            break;
        }
    }
    printf("%d
",res);
    return 0;
}

poj 3061 제목: 하위 서열 의 길 이 를 구 합 니 다. 이 하위 서열 의 합 은 지정 한 값 limit 보다 크 고 길이 가 가장 작 아야 합 니 다. 이 서열 의 최소 길 이 를 구 해 야 합 니 다.
사고: 위 와 같이 두 개의 커서 를 설정 하고 왼쪽 에서 오른쪽으로 O (n) 를 한 번 스 캔 하면 됩 니 다.사전 처리 로 n 항 과 배열 을 구하 면 위 에서 처리 하 는 것 이 더 편리 합 니 다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s));
#define N 100005
int s[N],n,m,T;
int main(){
    scanf("%d",&T);
    while(T--){
        int i,j,res=INF,now = 0;
        scanf("%d %d",&n,&m);
        for(i = 1;i<=n;i++)
            scanf("%d",&s[i]);
        for(i = 1,j = 0;j<=n;){
            while(now<m && j<n)
                now += s[++j];
            if(now<m && j>=n)
                break;
            res = min(res,j-i+1);
            while(now >= m && i<j)
                now -= s[i++];
            if(now>=m && i==j){
                res = 1;
                break;
            }
            res = min(res,j-i+2);
        }
        if(res == INF)
            printf("0
");
        else
            printf("%d
",res);
    }
    return 0;
}