fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <chrono>
  6. #include <random>
  7. #include <iomanip>
  8.  
  9. using namespace std;
  10.  
  11. // Cấu trúc lưu hộ gia đình
  12. struct Item {
  13.     double a;
  14.     int id;
  15. };
  16.  
  17. // Hàm xoá nhanh 1 phần tử khỏi vector (O(V))
  18. void remove_from_group(vector<int>& vec, int val) {
  19.     for (int i = 0; i < (int)vec.size(); ++i) {
  20.         if (vec[i] == val) {
  21.             vec[i] = vec.back();
  22.             vec.pop_back();
  23.             return;
  24.         }
  25.     }
  26. }
  27.  
  28. int main() {
  29.     // Tối ưu I/O
  30.     ios_base::sync_with_stdio(false);
  31.     cin.tie(NULL);
  32.  
  33.     int N;
  34.     double L;
  35.     if (!(cin >> N >> L)) return 0;
  36.  
  37.     vector<Item> items(N + 1);
  38.     vector<double> a(N + 1);
  39.     for (int i = 1; i <= N; ++i) {
  40.         cin >> items[i].a;
  41.         items[i].id = i;
  42.         a[i] = items[i].a;
  43.     }
  44.  
  45.     // BƯỚC 1: SẮP XẾP VÀ QUY HOẠCH ĐỘNG (DP) ĐỂ TÌM BASELINE TỐT
  46.     sort(items.begin() + 1, items.end(), [](const Item& x, const Item& y) {
  47.         return x.a < y.a;
  48.     });
  49.  
  50.     vector<double> dp(N + 1, 1e18);
  51.     vector<int> trace(N + 1, 0);
  52.     dp[0] = 0.0;
  53.  
  54.     for (int i = 1; i <= N; ++i) {
  55.         for (int j = 0; j < i; ++j) {
  56.             double S = 0;
  57.             for (int m = j + 1; m <= i; ++m) S += items[m].a;
  58.  
  59.             double H = S / L;
  60.             double cost = 0;
  61.             for (int m = j + 1; m <= i; ++m) {
  62.                 cost += abs(H - items[m].a / H);
  63.             }
  64.  
  65.             if (dp[j] + cost < dp[i]) {
  66.                 dp[i] = dp[j] + cost;
  67.                 trace[i] = j;
  68.             }
  69.         }
  70.     }
  71.  
  72.     // Truy vết DP để lấy phân hoạch ban đầu
  73.     vector<int> initial_group(N + 1);
  74.     int curr = N;
  75.     int g_id = 0;
  76.     while (curr > 0) {
  77.         int prev = trace[curr];
  78.         for (int i = prev + 1; i <= curr; ++i) {
  79.             initial_group[items[i].id] = g_id; // Đưa về index ban đầu của hộ
  80.         }
  81.         g_id++;
  82.         curr = prev;
  83.     }
  84.  
  85.     // BƯỚC 2: SIMULATED ANNEALING (SA)
  86.     vector<int> group_of = initial_group;
  87.     vector<vector<int>> members(N); // Tối đa N dải đất
  88.     vector<double> sum_group(N, 0.0);
  89.     vector<double> group_cost(N, 0.0);
  90.  
  91.     for (int i = 1; i <= N; ++i) {
  92.         members[group_of[i]].push_back(i);
  93.         sum_group[group_of[i]] += a[i];
  94.     }
  95.  
  96.     auto recalc_group = [&](int g) {
  97.         if (members[g].empty()) {
  98.             sum_group[g] = 0;
  99.             group_cost[g] = 0;
  100.             return;
  101.         }
  102.         double S = 0;
  103.         for (int u : members[g]) S += a[u];
  104.         sum_group[g] = S;
  105.         double H = S / L;
  106.         double c = 0;
  107.         for (int u : members[g]) c += abs(H - a[u] / H);
  108.         group_cost[g] = c;
  109.     };
  110.  
  111.     double current_total_cost = 0;
  112.     for (int g = 0; g < N; ++g) {
  113.         recalc_group(g);
  114.         current_total_cost += group_cost[g];
  115.     }
  116.  
  117.     double best_cost = current_total_cost;
  118.     vector<int> best_group_of = group_of;
  119.  
  120.     mt19937 rng(1337); // Seed cố định để dễ debug
  121.     auto get_time = []() {
  122.         return (double)clock() / CLOCKS_PER_SEC;
  123.     };
  124.  
  125.     double start_time = get_time();
  126.     double TIME_LIMIT = 4.8; // Chạy 4.8s để an toàn trong giới hạn 5s
  127.     double T_start = 100.0;
  128.     double T_end = 1e-6;
  129.  
  130.     while (true) {
  131.         double elapsed = get_time() - start_time;
  132.         if (elapsed > TIME_LIMIT) break;
  133.  
  134.         // Tính nhiệt độ hiện tại (giảm dần)
  135.         double progress = elapsed / TIME_LIMIT;
  136.         double current_T = T_start * pow(T_end / T_start, progress);
  137.  
  138.         int type = rng() % 2; // 0: Move, 1: Swap
  139.  
  140.         if (type == 0) {
  141.             // MOVE: Chuyển 1 phần tử sang nhóm khác
  142.             int u = uniform_int_distribution<int>(1, N)(rng);
  143.             int g_old = group_of[u];
  144.             int g_new = uniform_int_distribution<int>(0, N - 1)(rng);
  145.  
  146.             if (g_old == g_new) continue;
  147.  
  148.             // Đánh giá nhanh O(|V|)
  149.             double cost_old_new = 0;
  150.             if (members[g_old].size() > 1) {
  151.                 double H_old = (sum_group[g_old] - a[u]) / L;
  152.                 for (int x : members[g_old]) {
  153.                     if (x != u) cost_old_new += abs(H_old - a[x] / H_old);
  154.                 }
  155.             }
  156.  
  157.             double H_new = (sum_group[g_new] + a[u]) / L;
  158.             double cost_new_new = abs(H_new - a[u] / H_new);
  159.             for (int x : members[g_new]) {
  160.                 cost_new_new += abs(H_new - a[x] / H_new);
  161.             }
  162.  
  163.             double delta = (cost_old_new + cost_new_new) - (group_cost[g_old] + group_cost[g_new]);
  164.  
  165.             // Xác suất chấp nhận
  166.             if (delta < 0 || exp(-delta / current_T) > uniform_real_distribution<double>(0.0, 1.0)(rng)) {
  167.                 group_of[u] = g_new;
  168.                 remove_from_group(members[g_old], u);
  169.                 members[g_new].push_back(u);
  170.                 recalc_group(g_old);
  171.                 recalc_group(g_new);
  172.                 current_total_cost += delta;
  173.  
  174.                 if (current_total_cost < best_cost) {
  175.                     best_cost = current_total_cost;
  176.                     best_group_of = group_of;
  177.                 }
  178.             }
  179.         } else {
  180.             // SWAP: Đổi chỗ 2 phần tử ở 2 nhóm khác nhau
  181.             int u = uniform_int_distribution<int>(1, N)(rng);
  182.             int v = uniform_int_distribution<int>(1, N)(rng);
  183.             int g_old = group_of[u];
  184.             int g_new = group_of[v];
  185.  
  186.             if (g_old == g_new) continue;
  187.  
  188.             double H_old = (sum_group[g_old] - a[u] + a[v]) / L;
  189.             double cost_old_new = abs(H_old - a[v] / H_old);
  190.             for (int x : members[g_old]) {
  191.                 if (x != u) cost_old_new += abs(H_old - a[x] / H_old);
  192.             }
  193.  
  194.             double H_new = (sum_group[g_new] - a[v] + a[u]) / L;
  195.             double cost_new_new = abs(H_new - a[u] / H_new);
  196.             for (int x : members[g_new]) {
  197.                 if (x != v) cost_new_new += abs(H_new - a[x] / H_new);
  198.             }
  199.  
  200.             double delta = (cost_old_new + cost_new_new) - (group_cost[g_old] + group_cost[g_new]);
  201.  
  202.             if (delta < 0 || exp(-delta / current_T) > uniform_real_distribution<double>(0.0, 1.0)(rng)) {
  203.                 group_of[u] = g_new;
  204.                 group_of[v] = g_old;
  205.                 remove_from_group(members[g_old], u);
  206.                 remove_from_group(members[g_new], v);
  207.                 members[g_old].push_back(v);
  208.                 members[g_new].push_back(u);
  209.                 recalc_group(g_old);
  210.                 recalc_group(g_new);
  211.                 current_total_cost += delta;
  212.  
  213.                 if (current_total_cost < best_cost) {
  214.                     best_cost = current_total_cost;
  215.                     best_group_of = group_of;
  216.                 }
  217.             }
  218.         }
  219.     }
  220.  
  221.     // Đưa ra output
  222.     vector<vector<int>> final_groups(N);
  223.     for (int i = 1; i <= N; ++i) {
  224.         final_groups[best_group_of[i]].push_back(i);
  225.     }
  226.  
  227.     int k_used = 0;
  228.     for (int i = 0; i < N; ++i) {
  229.         if (!final_groups[i].empty()) k_used++;
  230.     }
  231.  
  232.     // In chi phí nhỏ nhất (có thể làm tròn tới 6 chữ số thập phân)
  233.     cout << fixed << setprecision(6) << best_cost << "\n";
  234.  
  235.     // In ra cách chia: số nhóm k, sau đó mỗi nhóm in ra số hộ và id của các hộ
  236.     cout << k_used << "\n";
  237.     for (int i = 0; i < N; ++i) {
  238.         if (!final_groups[i].empty()) {
  239.             cout << final_groups[i].size();
  240.             for (int x : final_groups[i]) cout << " " << x;
  241.             cout << "\n";
  242.         }
  243.     }
  244.  
  245.     return 0;
  246. }
Success #stdin #stdout 4.81s 5312KB
comments (?)
stdin
copy 
8 53
100 150 200 250 300 350 400 500
stdout
copy 
53.140461
3
3 1 2 3
3 4 5 6
2 7 8
https://ideone.com/9fXsE7
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!