E. Pencils and Boxes

题目链接

Educational Codeforces Round 44 (Rated for Div. 2)--E. Pencils and Boxes

题解

中档题,题意大概是给定一串数字,问能否分成多个每部分不小于k的部分且每部分最大最小值之差不大于k。
因为连续大小的的数放置在一起可以保证最大最小值之差尽可能小,所以先将数排序。之后使用递推判断即可。满足两个条件的区间要么是一个连续的区间,要么不存在,如果这个区间内有任意一个位置作为结尾可行,则这个位置作为结尾可行。最后直接判断最后一个数字即可。注意要用二分来判断快速查询区间,不然有可能会被卡时间。
据说这题好像正解该是树状数组然而我并不会orz。

代码

#include <iostream>
#include <stdlib.h>
#include <algorithm>

using namespace std;
int a[500005];
int isyes[500005];
int n, d, k,cache;
int find(int maxt,int l,int r){
    if (a[(l+r)/2]<maxt&&a[(l+r)/2+1]>=maxt)return (l+r)/2;
    else if (a[(l+r)/2]>=maxt)return find(maxt,l,(l+r)/2-1);
    else if (a[(l+r)/2+1]<maxt)return find(maxt,(l+r)/2+1,r);
}
bool func(int a, int b) {
    return a < b;
}
int main() {
    cin >> n >> k >> d;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(&a[1],&a[n+1],func);
    for (int i = k; i <= n; i++) {
        if (a[i] - a[1] <= d)isyes[i] = isyes[i - 1] + 1;
        else {
            cache = i;
            break;
        }
    }
    /*for (int i = 1; i <= n; i++) {
        cout << isyes[i]<<' ';
    }
    cout<<endl;
    cout<<cache<<endl;*/
    if (cache==0)cache=n+1;
    for (int i = cache; i <= n; i++) {
        int pos=lower_bound(a+1,a+n+1,a[i]-d)-a-1;
        if (pos>i-k){
                isyes[i]=isyes[i-1];
                continue;
        }
        //cout<<pos<<' '<<a[i]<<' '<<d<<endl;
        if (isyes[i-k]-isyes[pos-1]>0)isyes[i]=isyes[i-1]+1;
        else isyes[i]=isyes[i-1];
        /*for (int j = i-k+1; a[i] - a[j] <= d; j--) {
            if (isyes[j - 1]) {
                isyes[i] = true;
                break;
            }
        }*/
    }
    isyes[n]-isyes[n-1]>0 ? cout << "YES" : cout << "NO";
}

标签: dp, greedy, binary search, two pointers, data structures

添加新评论