bzoj4582[Usaco2016 Open]Diamond Collector
题意：
n个钻石，每个都有一个大小，现在将其装进2个盒子里，每个盒子里的钻石最大的与最小的大小不能超过k，问最多能装多少个。n最大50000。
题解：
我真傻，真的~首先对大小排序，然后找以i为左端点的可装区间，这个操作两个指针就可以搞，我却以为要二分查找。预处理完了，因为不交错的区间肯定比交错的区间优，所以从n到1递推一下从n到i最大的区间大小是多少，然后枚举每个区间，找到当前区间大小加上右端点+1到n中最大的区间大小中的最大值输出即可。我却以为要找与最大区间不交错的第二大区间，结果WA了好几发，才发现这是错误的贪心QAQ
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 60000
using namespace std; int n,k,sz[maxn],r,cnt[maxn],mx[maxn];
int main(){
scanf("%d%d",&n,&k); inc(i,,n)scanf("%d",&sz[i]); sort(sz+,sz+n+); r=;
inc(i,,n){
while(r<=n&&sz[r]-sz[i]<=k)r++; cnt[i]=r-i;
}
mx[n+]=; dec(i,n,)mx[i]=max(mx[i+],cnt[i]);
int ans=; inc(i,,n)ans=max(ans,cnt[i]+mx[i+cnt[i]]); printf("%d",ans);
return ;
}
20160519