Submission #1275158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275158		vk3601h	Sirni (COCI17_sirni)	C++20	0 / 140	5093 ms	5236 KiB

sirni

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>

// 提高IO效率，竞赛编程常用
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 函数：寻找将 x 连接到已访问集合 S 的最小代价
long long find_min_cost(int x, const std::set<int>& visited) {
    // 1. 检查是否存在免费连接（x的约数在集合中）
    // 遍历x的所有约数
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            if (visited.count(i)) {
                return 0; // 找到约数，代价为0
            }
            if (i != x / i && visited.count(x / i)) {
                return 0; // 检查另一个约数
            }
        }
    }

    long long min_cost = x; // 初始化最小代价为x本身（%1的最大可能值）
    int sqrt_x = sqrt(x);

    // 2. 检查大值连接 (y > sqrt(x))
    // 通过遍历 k = floor(x/y) 来覆盖所有 y > sqrt(x) 的情况
    for (int k = 1; k <= sqrt_x; ++k) {
        int upper_bound = x / k;
        // 在visited集合中找到 <= upper_bound 的最大元素
        auto it = visited.upper_bound(upper_bound);
        if (it != visited.begin()) {
            --it;
            int y = *it;
            min_cost = std::min(min_cost, (long long)x % y);
        }
    }

    // 3. 检查小值连接 (y <= sqrt(x))
    // 直接遍历所有可能的y值
    for (int y = 1; y <= sqrt_x; ++y) {
        if (visited.count(y)) {
            min_cost = std::min(min_cost, (long long)x % y);
        }
    }

    return min_cost;
}

int main() {
    fast_io();

    int n;
    std::cin >> n;
    std::vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
    }

    // 将卡片按数值从小到大排序
    std::sort(p.begin(), p.end());

    std::set<int> visited; // 使用有序集合来存储已处理的卡片数值
    visited.insert(p[0]);  // 将最小的卡片放入集合

    long long total_cost = 0;

    // 依次处理剩下的卡片
    for (int i = 1; i < n; ++i) {
        int x = p[i];
        // 寻找连接x的最小代价
        long long min_weight = find_min_cost(x, visited);
        total_cost += min_weight;
        // 将x加入已访问集合
        visited.insert(x);
    }

    std::cout << total_cost << std::endl;

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14