[ZOJ 3301 Make Pair]排序、贪心

【题目大意】

给偶数个人分组，使得组员的体重相差值之和最小。

【算法分析】

该次月赛的送分题。

显然，排序以后按顺序两两匹配即可。

证明：

若a<=b<=c<=d

即证明：d-c+b-a<=d-a+c-b

推导出：b<=c

符合条件，所以得证。

【CODE】

#include #include #include #include #include using namespace std;
struct datatype{int d,pos;}a[11111];
int n;

inline bool cmp(datatype x,datatype y){
    return x.d}   

int main(){
    int tc=0;
    while (scanf("%d",&n)!=EOF){
        tc++;
        if (tc!=1) printf("n");
        for (int i=1;i<=n;i++) scanf("%d",&a[i].d);
        for (int i=1;i<=n;i++) a[i].pos=i;
        sort(&a[1],&a[n+1],cmp);
        for (int i=1;i          printf("%d %dn",a[i].pos,a[i+1].pos);
    }   
}