洛谷 P3143 [USACO16OPEN]钻石收藏家Diamond Collector 题解【前缀和】【two-pointer】【贪心】

作者: wjyyy 分类: two-pointer,解题报告,贪心 发布时间: 2018-08-30 17:46

点击量:34

 

    解法众多的一道毒瘤题?

题目描述

奶牛Bessie很喜欢闪亮亮的东西(Baling~Baling~),所以她喜欢在她的空余时间开采钻石!她现在已经收集了\(N\)颗不同大小的钻石,现在她想在谷仓的两个陈列架上摆放一些钻石。

Bessie想让这些陈列架上的钻石保持相似的大小,所以她不会把两个大小相差\(K\)以上的钻石同时放在一个陈列架上(如果两颗钻石的大小差值为\(K\),那么它们可以同时放在一个陈列架上)。现在给出\(K\),请你帮Bessie确定她最多一共可以放多少颗钻石在这两个陈列架上。

输入输出格式

输入格式:
第一行两个整数\(N,K\)。

接下来\(N\)行,每行一个正整数\(a_i\),表示第\(i\)颗钻石的大小。

输出格式:
一行一个正整数,表示Bessie最多能放钻石的数量。

输入输出样例

输入样例1:

7 3
10
5
1
12
9
5
14 

输出样例1:

5

说明

对于\(100\%\)的数据,\(N\le50,000,a_i\le1,000,000,000,\ K\le1,000,000,000\)。

题解:

    其实这个题可以用暴力线段树,也可以用DP单调栈。不过想到一种RMQ方法,也可以完成这道题。

    题目要求每个陈列架中的元素最大-最小不超过定值\(k\),可以贪心地认为,它们处在一个区间里,下界是一个元素\(a_i\),上界是\(a_i+k\),这样避免了下界的浪费。同时因为没有顺序的要求,所以可以排序。

    而我们要选择两个区间,就得使两个区间并中的元素个数最多。可以考虑用一个数组\(f[i]\)存下以\(a[i]\)开始,长度为\(k\)的区间有多少个数。

    当两个区间不相交的时候,答案肯定就是两个数相加。当两个区间相交的时候呢?我们知道,相交肯定没有不相交优。如果两个区间相交了,可以把稍微靠后的区间向后平移一段,这样不会损失任何区间,反而可能会使答案变优。

    所以枚举左边的区间,然后在左区间右端点以右找最大值。可以直接维护后缀最大值来转移,用\(mus[i]\)表示\(\max\limits_{j\in[i,n]}f[i]\),就可以在\(O(n)\)的时间内转移,并在总时间\(O(n\log n)\)内完成全部过程。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
int mus[51000];//后缀最大值
int a[51000];
int b[51000];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    std::sort(b+1,b+1+n);
    int t1=n;
    for(int i=n;i;--i)
    {
        while(b[t1]>b[i]+k)
            --t1;
        a[i]=t1-i+1;//用two-pointer统计上界
        mus[i]=std::max(mus[i+1],a[i]);
    }

    int ans=0;
    for(int i=1;i<=n;++i)
    {
        int ans1=0;
        ans1=mus[i+a[i]];//转移最大值
        ans=std::max(ans,a[i]+ans1);
    }
    printf("%d\n",ans);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */