The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——D. Dropshipping（正过来看，ddl 是 ddl，也就是截止时间，但是反过来看，ddl 是激活时间）

题目大意

一开始对题面的理解有问题，我以为他可以保留折扣机会，但是实际上不行，不能保留。

题目描述

给定 $N$ 个顾客的商品购买需求，第 $i$ 个需求对应的商品价格为偶数 $A_i$。

商店有一项优惠活动：每完成 $X$ 次全价购买后，下一次购买单件商品可以获得 50% 的折扣。此次打折购买不计入下一次获取折扣所需的 $X$ 次全价购买中。

你可以自由决定这 $N$ 件商品的购买顺序。但为了满足发货时间限制，第 $i$ 个需求对应的商品，必须在你的前 $i+K$ 次购买中完成。

由于顾客已经提前支付了全额费用，你通过折扣节省下来的金额即为你个人的利润。请计算并输出你能获得的最大总利润（即所有打折购买商品原价的一半的总和）。

输入格式

第一行包含三个整数 $N$、$X$ 和 $K$（$1 \le N, X \le 2 \times 10^5$，$0 \le K \le 2 \times 10^5$），分别表示需求数量、获得折扣所需的全价购买次数，以及延迟发货的限制参数。
第二行包含 $N$ 个偶数 $A_1, A_2, \dots, A_N$（$2 \le A_i \le 10^9$），依次表示每个需求商品的价格。

输出格式

输出一个整数，表示你能获得的最大总利润。

样例 1

输入：

3 1 0
6 4 14

输出：

2

样例 1 解释

由于 $K=0$，第 $i$ 个需求必须在第 $i$ 次购买时完成。因此购买顺序被严格固定为 [6, 4, 14]。只有第二次购买（价格为 $4$）可以享受半价折扣，能获得的最大利润为 $4 / 2 = 2$。

样例 2

输入：

3 1 1
6 4 14

输出：

7

样例 2 解释

由于 $K=1$，第 $i$ 个需求必须在前 $i+1$ 次购买内完成。合法的购买顺序包括 [6, 4, 14]、[6, 14, 4]、[4, 6, 14] 以及 [14, 6, 4]。
其中，顺序 [6, 14, 4] 是最优的：在花费全价购买价格为 $6$ 的商品后，可以对价格为 $14$ 的商品使用折扣，从而获得最大利润 $14 / 2 = 7$。

思路讲解

gemini 的正难则反

问题描述 (Problem Description)

给定 $N$ 个顾客的商品购买需求，第 $i$ 个需求对应的商品价格为偶数 $A_i$。商店有折扣规则：每完成 $X$ 次全价购买后，下一次单件购买将享受半价折扣。你可以自由决定购买顺序，但为了保证发货时间，第 $i$ 个需求必须在你的前 $i+K$ 次购买内完成。通过折扣省下来的钱即为你的利润，要求计算并输出能够获得的最大总利润。

解题思路 (Chosen Approach)

这是一个带有截止时间（Deadline）限制的最优调度问题。
对于原始数组中的第 $i$ 个商品，它最迟必须在第 $i+K$ 次购买时被处理。因此，对于每个商品 $i$，它的有效放置区间为 $[1, \min(N, i+K)]$。令截止位置 $d_i = \min(N, i+K)$。
我们可以从后往前（从第 $N$ 次购买到第 $1$ 次购买）逆序来确定每次购买的商品：

1. 候选池特性：当我们在决策第 $j$ 个位置放哪个商品时，所有截止位置 $d_i \ge j$ 的商品都可以放在这里。我们将这些商品加入候选池。
2. 无差异的灵活性：对于此时存在于候选池中的任意商品，因为它们的 $d_i \ge j$，它们显然也满足 $d_i > j-1$。这意味着，候选池中的任何商品对于更早的位置（$1$ 到 $j-1$）都是绝对合法的。因此，在当前位置做选择时，我们不需要担心某个商品是否必须留给前面的特定位置，它们的灵活性是完全等价的。
3. 贪心选择：

• 如果当前位置 $j$ 是折扣位（即 $j \pmod{X+1} == 0$），为了让利润最大化，我们应该从候选池中挑出价格最大的商品用于打折。
• 如果当前位置 $j$ 是全价位，我们无法从该位置获得利润，为了把更高价格的商品保留给前面的折扣位，我们应该从候选池中挑出价格最小的商品消耗掉。

代码实现 (Code Implementation)

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

using namespace std;

int main() {
    // 优化标准输入输出流以提高执行速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, X, K;
    if (!(cin >> N >> X >> K)) return 0;

    // A 存储每个商品的价格
    vector<long long> A(N + 1);
    // add_at[j] 存储截止位置恰好为 j 的所有商品价格
    vector<vector<long long>> add_at(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        int d_i = min(N, i + K);
        add_at[d_i].push_back(A[i]);
    }

    // pool 作为候选池，动态维护当前所有合法的可用商品价格
    multiset<long long> pool;
    long long max_profit = 0;

    // 从最后一次购买逆序推演到第一次购买
    for (int j = N; j >= 1; --j) {
        // 当时间倒退到 j 时，截止位置恰好为 j 的商品进入可用候选池
        for (long long price : add_at[j]) {
            pool.insert(price);
        }

        // 判断当前位置 j 是否为折扣位
        // 规则是 X 个全价后跟 1 个半价，所以折扣位恰好是 X+1 的倍数
        if (j % (X + 1) == 0) {
            // 折扣位：贪心选择候选池中价格最大的商品
            auto it = prev(pool.end());
            max_profit += (*it) / 2;
            pool.erase(it);
        } else {
            // 全价位：贪心选择候选池中价格最小的商品，将大数字留给前面的折扣位
            auto it = pool.begin();
            pool.erase(it);
        }
    }

    cout << max_profit << "\\n";

    return 0;
}

代码解释与复杂度分析 (Explanation of the code and its complexity analysis)

代码逻辑分析：

1. 数据预处理：我们首先遍历所有 $N$ 个输入商品，算出每个商品的最后期限 d_i = min(N, i + K)。随后我们将这些价格通过 add_at 数组归类（类似于桶排序），以便逆序处理时能够以 $O(1)$ 的时间查找到在特定位置新解锁的商品。
2. 贪心维护：使用 std::multiset<long long> 来作为可用商品的动态候选池。外层循环从 $N$ 倒序遍历至 $1$。每次到达一个新的位置 $j$，我们将 add_at[j] 中的元素全部加入池中。
3. 利润计算：根据取模逻辑判断当前轮次，折扣直接加到 max_profit 中。multiset 会自动维护元素有序，使得获取最大值 (prev(pool.end())) 和最小值 (pool.begin()) 都极为高效。需要注意的是，一定要用迭代器删除（erase(it)），以防止误删同价格的其他商品。
   复杂度分析：

• 时间复杂度 (Time Complexity): $O(N \log N)$。预处理划分数组只需 $O(N)$ 的时间；逆序遍历的循环一共执行 $N$ 次，在整个过程中，每个价格必定被插入到 multiset 一次，并且被删除一次。红黑树（multiset）的插入与删除操作单次耗时 $O(\log N)$。故总时间复杂度为 $O(N \log N)$，这在 $N \le 2 \times 10^5$ 且时限为 1 秒的要求下能够极速运行并通过。
• 空间复杂度 (Space Complexity): $O(N)$。使用了若干个长度为 $N+1$ 的 vector 来存储数据，同时 multiset 中最多同时存储 $N$ 个元素。总共占用的内存远低于 1024 MB 的内存限制。

呃，这个问他问的太早了。其实知道了，不能够保留这个折扣机会，那么其实倒过来看就非常 easy 的一件事情了。

为什么反向处理呢？我们不难发现，一个数，更早被处理完全没有任何问题，但是不能更晚被处理。

或者，可以这么说，正过来看，ddl 是 ddl，也就是截止时间，但是反过来看，ddl 是激活时间。

ll gen_ans(const map<ll, vector<ll> > &ddl_price, ll N, ll X) {
    ll ans = 0;
    // gen_sorted_st(ddl_price, st1);
    multiset<ll> st_small;
    multiset<ll,greater<>> st_big;
    // gen_sorted_st(ddl_price, st2);
    for (int i = N; i >= 1; --i) {
        auto it = ddl_price.find(i);
        // 有没有 ddl 是 i 的商品？我们对其进行激活
        if (it != ddl_price.end()) {
            for (auto price: it->second) {
                st_big.insert(price);
                st_small.insert(price);
            }
        }
        if (i % (X + 1) == 0) {
		        // 折扣的时候选择大的数字
            ll add=*st_big.begin();
            ans+=add/2;
            st_erase(st_small,st_big,add);
        } else {
		        // 平时抛弃小的数字
            ll add=*st_small.begin();
            st_erase(st_small,st_big,add);
        }
    }
    return ans;
}

AC代码

AC
https://codeforces.com/gym/106416/submission/368218310

源代码

/**
 * Problem: D. Dropshipping
 * Contest: The 2026 ICPC Latin America Championship
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106416/problem/D
 * Created: 2026-03-24 14:31:27
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
map<ll, vector<ll> > gen_goods_ddl(const vector<ll> &A, ll N, ll K) {
    map<ll, vector<ll> > res;
    for (int i = 1; i <= N; ++i) {
        ll ddl = min(i + K, N);
        res[ddl].push_back(A[i]);
    }
    return res;
}

// struct Ddl_price {
//     ll ddl;
//     ll price;
// };
//
// struct Cmp1 {
//     bool operator()(const Ddl_price &a, const Ddl_price &b) const {
//         if (a.ddl != b.ddl) return a.ddl > b.ddl;
//         return a.price > b.price;
//     }
// };
//
// struct Cmp2 {
//     bool operator()(const Ddl_price &a, const Ddl_price &b) const {
//         if (a.ddl != b.ddl) return a.ddl > b.ddl;
//         return a.price < b.price;
//     }
// };
//
// void gen_sorted_st(const map<ll, vector<ll> > &ddl_price, auto &st) {
//     for (auto it = ddl_price.rbegin(); it != ddl_price.rend(); ++it) {
//         ll ddl = it->first;
//         for (auto price: it->second) {
//             st.insert({ddl, price});
//         }
//     }
// }
void st_erase(auto &st_small, auto &st_big, ll x) {
    auto its = st_small.find(x);
    st_small.erase(its);
    auto itb = st_big.find(x);
    st_big.erase(itb);
}

ll gen_ans(const map<ll, vector<ll> > &ddl_price, ll N, ll X) {
    ll ans = 0;
    // gen_sorted_st(ddl_price, st1);
    multiset<ll> st_small;
    multiset<ll,greater<>> st_big;
    // gen_sorted_st(ddl_price, st2);
    for (int i = N; i >= 1; --i) {
        auto it = ddl_price.find(i);
        if (it != ddl_price.end()) {
            for (auto price: it->second) {
                st_big.insert(price);
                st_small.insert(price);
            }
        }
        if (i % (X + 1) == 0) {
            ll add=*st_big.begin();
            ans+=add/2;
            st_erase(st_small,st_big,add);
        } else {
            ll add=*st_small.begin();
            st_erase(st_small,st_big,add);
        }
    }
    return ans;
}

void Solve() {
    ll N, X, K;
    cin >> N >> X >> K;
    vector<ll> A(N + 2);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    auto ddl_price = gen_goods_ddl(A, N, K);
    cout << gen_ans(ddl_price, N, X) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106416/submission/368218310

*/

心路历程（WA，TLE，MLE……）