[1]

K-Knowledge Test about Match_2021牛客暑期多校训练营1 (nowcoder.com)

随机化贪心 第一次遇到

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mx = 1e3 + 10;
 5 int n, t;
 6 inline double dd(int a, int b){
 7     return sqrt(abs(a-b));
 8 }
 9 int a[mx], b[mx];
10 double bj(int i1, int i2){
11     return dd(a[i1],b[i1])+dd(a[i2],b[i2])-dd(a[i1],b[i2])- dd(a[i2],b[i1]);
12 }
13 void solve(){
14     scanf("%d", &t);
15     for(int lp=1;lp<=t;lp++){
16         scanf("%d", &n);
17         for(int i=1;i<=n;i++){
18             a[i]=i-1;
19             scanf("%d", &b[i]);
20         }
21 //        printf("-------------------over-------------------\n");
22         for(int time=1;time<=3;time++){
23             bool has=false;
24             for(int i=1;i<=n;i++){
25                 for(int j=i+1;j<=n;j++){
26                     double ans= bj(i,j);
27                     if(ans>0){
28                         has=true;
29                         swap(b[i], b[j]);
30                     }
31                 }
32             }
33             if(has==false)break;
34         }
35         for(int i=1;i<=n;i++){
36             if(i!=1)printf(" ");
37             printf("%d", b[i]);
38         }
39         puts("");
40     }
41 }
42 int main(){
43     solve();
44     return 0;
45 }

View Code