牛客一 K-Knowledge Test about Match

給出一組bi，將其順序進(jìn)行變換，使得$min{\sum }_{i=1}^n\sqrt{|b_i?i|}$，將變換順序的數(shù)組輸出。要求與正確的答案的差值在4%以內(nèi)。
數(shù)據(jù)范圍：一共T組數(shù)據(jù)，100 <= T <= 500，10 <= n <= 1000，sum n <= 4e4

開(kāi)始是想寫(xiě)隨機(jī)算法的，不過(guò)數(shù)據(jù)量有點(diǎn)大，隨機(jī)數(shù)生成與取模所帶來(lái)的時(shí)間消耗沒(méi)法在規(guī)定時(shí)間內(nèi)跑出正確答案。

后面按照sol當(dāng)中給出的那種多次n方循環(huán)比較交換的方法過(guò)的，但是我還是念念不忘我的隨機(jī)數(shù)。

#include <bits/stdc++.h> using namespace std;const int N = 1e3 + 10, mx = 1e4; int b[N]; double sq[N];void init() {for (int i = 0; i < N; i ++)sq[i] = sqrt(1.0 * i); }int main() {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);srand(time(0));int T = 1;cin >> T;init();while (T --){int n;cin >> n;for (int i = 0; i < n; i ++)cin >> b[i];int tot = 10;while (tot --){for (int x = 0; x < n; x ++)for (int y = x + 1; y < n; y ++)if (sq[abs(b[x] - x)] + sq[abs(b[y] - y)] > sq[abs(b[x] - y)] + sq[abs(b[y] - x)])swap(b[x], b[y]);}for (int i = 0; i < n; i ++){cout << b[i];if (i < n - 1)cout << " ";}cout << "\n";}return 0; } 與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的牛客一 K-Knowledge Test about Match的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。