【题目描述】 奶牛贝茜总是喜欢发光的东西，开采钻石是它的一项业余爱好。它收集了n(n≤100,000)颗大小不等的钻石。它想安排它们在一对谷仓的展示柜里展览。贝茜希望每个展示柜里的钻石大小相仿，它决定大小差距超过k的两颗钻石不能在同一个展示柜（大小差距正好是k的两颗钻石可以在同一个展示柜）。现在给出k，请帮助贝茜决定两个展示柜中的钻石最大总数量。 【输入格式】 第一行包括n和k(0≤k≤1,000,000,000)。 下面n行，每行给出一个钻石的大小，所有钻石的大小不会超过1,000,000,000。 【输出格式】 一个正整数表示贝茜可以展览在两个展示柜里的钻石数量之和。 【输入样例】 7 3 10 5 1 12 9 5 14 【输出样例】 5 【样例说明】 第一个展示柜：5 5 第二个展示柜：10 12 9 共5个钻石 【分析】 单调队列+动态规划
uses math; var i,j,n,k,ans:longint; a,fl,fr:array[0..100001]of longint; procedure qsort(l,r:longint); var i,j,temp,mid:longint; begin i:=l; j:=r; mid:=a[(l+r) div 2]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; begin readln(n,k); for i:=1 to n do read(a[i]); qsort(1,n); i:=1; for j:=1 to n do begin while a[j]-a[i]>k do inc(i); fl[j]:=max(fl[j-1],j-i+1); end; j:=n; for i:=n downto 1 do begin while a[j]-a[i]>k do dec(j); fr[i]:=max(fr[i+1],j-i+1); end; for i:=1 to n-1 do ans:=max(ans,fl[i]+fr[i+1]);//枚举分割点 write(ans); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533541.html
相关资源：JAVA上百实例源码以及开源项目