T1
题目描述：
“OI-Fitter 健身训练营”的总教练正在为训练的组织问题发愁。按照流程安
排,营员们 2 人一组进行训练,但悬殊的个体差异让分配队伍的问题变得棘手。
为了评估营员之间差异的大小,总教练设立了这样一个指标:设营员共有 N。
名,每个人的健壮程度设为一个正整数 x[i] (i=1,2,3......)。将这N个数两两求
差并取绝对值,可得到如下的 M=C(n,2) 个数:
| x[s] - x[t] | ,1≤s<t≤N。
最终的“差异指标”设为这M个数的中位数。若M为偶数,则中位数视为第 M /2 小的数。
现给出营员的数量N和每人的健壮程度,请你帮总教练求出他们的“差异指标”。
输入格式：
每个测试文件含3~5组测试数据,以文件结束符 (EOF) 表示输入结束。
对于每组数据:
第一行是一个正整数 N;
第二行是 N 个正整数,第i个数为 x[i]。
输出格式：
对于每组测试数据,输出一行表示答案。
样例输入：
4
1 3 2 4
3
1 10 2
样例输出：
1
8
数据规模：
(30%)的数据:(3leq;N ;leq1000)
(100%)的数据:(3leq;Nleq;100,000,1leq; x_i;leq10^9)。
分析：
我们先考虑朴素算法，将每一个(;leftvert x_s-x_t ightvert;)求出来，再排一遍序，找出中位数，但这样的时间复杂度为(;O(n^2);)的，肯定会超时，我们想如何去优化。
似乎，这条路走到头了。我们肯定是无法在时间限制(;1s;)内求出来所有的(;leftvert x_s-x_t ightvert;)的，那我们是否可以不将其具体求出而能找到我们需要的答案的方法呢？
我们都想到了排序，而且(;leftvert x_s-x_t ightvert;)与(;x_i;)在序列中的顺序是没有关系的，反正每两个之间都有。那么我们为什么不可以将原(;x;)数组从小到大排序，之后……二分答案？
好像是可以的。
我们可以二分出一个值(;val;)，表示我们要求的答案中位数，在数组中寻找比每个(;x_i;)小(;val;)的数的个数(;cnt;)，如果比(;n imes (n-1)div 4;)大，那么就表示我们二分的(;val;)值小了，继续二分右区间，反之，二分左区间。很显然，(;cnt;)是单调递增的。
当然，即使小了，(;val;)也是我们的可能答案之一。
(Code)：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
#define ll long long
#define il inline
#define vocaloid(v) (v>='0'&&v<='9')
template <typename T>
il void read(T &x)
{
x=0;char v=getchar();
while(!vocaloid(v)) v=getchar();
while(vocaloid(v)) {x=(x<<1)+(x<<3)+v-'0';v=getchar();}
}
ll n,m,a[maxn],ans,l,r,mid;
il bool check(int val)
{
ll cnt=0;
for(int i=0;i<n;i++)
cnt+=n-(lower_bound(a,a+n,a[i]+val)-a);
return cnt>m;
}
int main()
{
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
while(scanf("%lld",&n)==1)
{
m=n*(n-1)>>2;
for(int i=0;i<n;i++) read(a[i]);
sort(a,a+n);
l=0,r=a[n-1]-a[0];
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld
",ans);
}
return 0;
}
T3 POJ-3666
分析：
取得最小值的必要条件:对于任意的(;i;),都存在(;j;)使得(;x_i=a_j;)。其中(;1leq i,jleq N;)。也就是
说,(;x_i;)的取值范围只可能是(;a_1,a_2,ldots,a_N;) 构成的集合(下文记为 (;S))。
我们先考虑单调不下降的情况。
我们记(;b;)数组来储存出现过的所有数（去了重），共有(;m;)个，并从小到大排序，然后进行dp。
我们记(;f_{i,j};)为前(;i;)个数单调不下降，且第(;i;)个数凑成(;b_j;)时的最小花费。
转移方程为：
但我们发现这样的化，时间复杂度为(;O(n^3);)的。
由于(;j;)是递增的，(;k;)也是，我们进行了很多重复的操作，所以我们可以用一个(;Min;)来储存当前(;1;)到当前(;j;)的(f_{i-1,k};)的最小值，可优化成：
这样，就优化成了(;O(n^2);)的，就可以通过啦！
(Code)：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+7;
#define inf 0x3f3f3f3f3f3f3f3f
#define il inline
#define vocaloid(v) (v>='0'&&v<='9')
#define ll long long
template <typename T>
il void read(T &x)
{
x=0;char v=getchar();
while(!vocaloid(v)) v=getchar();
while(vocaloid(v)) {x=(x<<1)+(x<<3)+v-'0';v=getchar();}
}
ll a[maxn],A[maxn],b[maxn],ans;
ll f[maxn][maxn],n,len=-inf,m;
il ll DP()
{
for(int i=1;i<=n;i++)
{
ll Min=inf;
for(int j=1;j<=m;j++)
{
Min=min(Min,f[i-1][j]);
f[i][j]=Min+abs(a[i]-b[j]);
}
}
ll res=inf;
for(int i=1;i<=m;i++) res=min(res,f[n][i]);
return res;
}
int main()
{
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
read(n);
for(int i=1;i<=n;i++) read(a[i]),A[i]=a[i];
sort(A+1,A+1+n);
for(int i=1;i<=n;i++)
if(A[i]!=len) b[++m]=A[i],len=A[i];
ans=DP();
memset(f,0,sizeof(f));
for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
ans=min(ans,DP());
printf("%lld
",ans);
return 0;
}