(2017 다 교 2) 1003 / hdu - 6047 Maximum Sequence (단조 로 운 대기 열 / 우선 대기 열)

나 를 찍 어 문 제 를 보다.
제목: 각각 두 개의 서열 a 와 b 를 제시 하고 규칙 에 따라 ai ≤ max {aj - j ☆ bk ≤ j
공식 문제 풀이: 예 처리: a i - = i, 가장 작은 b 부터 매번 가장 큰 것 을 선택 하면 반드시 결과 가 가장 크다 는 것 을 증명 하기 쉽다.범위 내 에서, 그래서 매번 a i - i 를 가능 한 한 크게 만 들 면, 큰 숫자 를 가능 한 한 빨리 사용 하고, 매번 가능 한 한 많은 숫자 를 고려 해 야 한다. 이렇게 얻 은 숫자 는 가능 한 한 크다. 그 러 니까 매번 구간 의 최고 치 를 구하 고, 답 을 더 하 는 것 이다. 욕심 의 사고 로 매번 요구 하 는 구간 의 하 계 는 단 조 롭 고 내 려 가지 않 기 때문에 단조 로 운 대열 로 O (n) 로 최적화 할 수 있다.의 복잡 도. 1 ≤ b i ≤ n 으로 인해 b 정렬 은 해시 정렬 (통 정렬) 으로 완성 할 수 있 습 니 다.
좀 더 살 펴 보면 이러한 욕심 이 있 을 때 a (n + 1)... a i 는 사실 단 조 롭 고 증가 하지 않 기 때문에 구간 의 최고 치 를 구 할 필요 가 없다. 첫 번 째 수 를 선택 할 때 가장 큰 것 을 선택 하고 뒤의 선택 순 서 는 최종 결과 와 무관 하 다.
분석: Contest 때 우선 대기 열 로 썼 는데 시간 초과 가 걱정 이 었 어 요. 나중에 생각해 봐 도 시간 초과 가 없 을 것 같 아 요. 팀 에 들 어 오 는 과정 이 모두 O (log2n) 였 는데 단조 로 운 대기 열 로 시간 을 절약 하 는 것 을 발 견 했 어 요.
참조 코드:
/ / 우선 대기 열

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

/ / 단조 로 운 대기 열

#include
#include
#include
#include
#include

using namespace std;
#define LL long long
const int mod = 1e9+7;
const int maxn = 250010;
int n;
int a[maxn];
int b[maxn];
struct Node{
    int id;
    int val;
};
Node q[maxn<<1];

int main()
{
    while( ~scanf("%d",&n))
    {
        int head = 0;
        int tail = 0;
        for( int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            if( tail == 0)
            {
                q[tail].id = i;
                q[tail++].val = a[i]-i;
            }
            else
            {
                while( head < tail && a[i]-i >= q[tail-1].val)
                    tail--;
                q[tail].id = i;
                q[tail++].val = a[i]-i;
            }
        }
        for( int i = 1; i <= n; i++)
            scanf("%d",&b[i]);
        sort(b+1,b+1+n);

        int p = 1;
        Node tmp;
        LL ans = 0;
        while( p <= n)
        {
            while( b[p] > q[head].id)
                head++;
            ans = (ans+q[head].val)%mod;
            tmp.id = p+n;
            tmp.val = q[head].val-(n+p);
            while( head < tail && tmp.val >= q[tail-1].val)
                tail--;
            q[tail++] = tmp;
            p++;
        }
        printf("%lld
",ans);

    }

    return 0;
}