签到题BDF

K

给定两个数组，一个数组是a={0,1,2,3...,n-1}，另一个是b={b0,b1,b2,b3...bn-1}，要求给b数组定一个排列方式，使得∑sqrt(abs(ai-bi))尽可能小。

n<=1000

数据100组到500组，b数组完全随机生成。

多组数据总误差在4%以内可被接受。

题解：

一开始是直接对b排序，依次填，但是不够优秀，因为这样会产生很多1，在根号下，这样是很亏的。

规避1，就先尽可能让a中的第bi位与bi配对。

剩下的，我采用的是顺序填，然后再两两判断交换后是否更优。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[50000],b[50000],c[50000],aa[50000],d[50000];
 4 int main()
 5 {
 6     freopen("test.in","r",stdin);
 7     int t;
 8     scanf("%d",&t);
 9     while (t)
10     {
11         t--;
12         int n;
13         scanf("%d",&n);
14         for (int i=0;i<=n;i++) b[i]=0;
15         int k=0;
16         for (int i=1;i<=n;i++) 
17         {
18             scanf("%d",&a[i]);
19             if (b[a[i]]) c[++k]=a[i];
20             b[a[i]]=1;
21         }
22         sort(c+1,c+k+1);
23         int l=0;
24         for (int i=0;i<=n;i++) if (b[i]) aa[i]=i;
25         for (int i=0;i<n;i++) if (!b[i])
26         {
27             l++;
28             d[l]=i;
29         }
30         double aa1=1000000000,aa2=0;
31         int aj=1;
32         for (int i=1;i<=l;i++)
33         {
34             aa2=0;
35             for (int j=1,p=i;j<=l;j++,p++)
36             {
37                 if (p==l+1) p=p-l;
38                 aa2=aa2+sqrt(abs(d[j]-c[p]));
39             }
40             if (aa2<=aa1)
41             {
42                 aa1=aa2;    
43                 aj=i;
44             }
45         }
46         aj=1;
47         for (int j=1,p=aj;j<=l;j++,p++) 
48         {
49             if (p==l+1) p=p-l;
50             aa[d[j]]=c[p];
51         }
52         for (int i=0;i<n;i++)
53         {
54             for (int j=i+1;j<n;j++)
55             {
56                 if (aa[i]==i||aa[j]==j) continue;
57                 if (sqrt(abs(aa[i]-i))+sqrt(abs(aa[j]-j))>=sqrt(abs(aa[j]-i))+sqrt(abs(aa[i]-j))) swap(aa[i],aa[j]);
58             }
59         }
60         for (int i=n-1;i>=0;i--)
61         {
62             for (int j=i-1;j>=0;j--)
63             {
64                 if (aa[i]==i||aa[j]==j) continue;
65                 if (sqrt(abs(aa[i]-i))+sqrt(abs(aa[j]-j))>sqrt(abs(aa[j]-i))+sqrt(abs(aa[i]-j))) swap(aa[i],aa[j]);
66             }
67         }
68         for (int i=0;i<n-1;i++) printf("%d ",aa[i]);
69         printf("%d\n",aa[n-1]);    
70     }
71 }