BZOJ 4582 [Usaco2016 Open]Diamond Collector：贪心【相差不超过k】

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4582

题意：

　　给你n个数。

　　让你将其中的一些数放入两个不同的集合中，并保证同一集合内两两元素相差不超过k。

　　问你两个集合中数字个数之和最大为多少。

 

题解：

　　贪心。

　　先将所有数字升序排序。

　　然后O(N)处理出ans[i]：

　　　　以i为起点，在一个集合中，往后最多能选多少个数。

　　再从后往前更新ans[i]和best：

　　　　以i以及i后面的点为起点，在一个集合中，往后最多能选多少个数。

　　　　ans[i] = max(ans[i], ans[i+1])

　　　　同时更新答案：best = max ans[i] + ans[i+ans[i]]

 

AC Code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 50005

using namespace std;

int n,k;
int best=0;
int a[MAX_N];
int ans[MAX_N];

void read()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
}

void solve()
{
    sort(a,a+n);
    int pos=0;
    for(int i=0;i<n;i++)
    {
        while(a[pos]-a[i]<=k && pos<n) pos++;
        ans[i]=pos-i;
    }
    ans[n]=0;
    for(int i=n-1;i>=0;i--)
    {
        best=max(best,ans[i]+ans[i+ans[i]]);
        ans[i]=max(ans[i],ans[i+1]);
    }
}

void print()
{
    cout<<best<<endl;
}

int main()
{
    read();
    solve();
    print();
}