The 2026 ICPC Latin America Championship(2026 拉丁美洲决赛)-Gym-106416——D. Dropshipping(正过来看,ddl 是 ddl,也就是截止时间,但是反过来看,ddl 是激活时间) · znzryb
## 题目大意

一开始对题面的理解有问题,我以为他可以保留折扣机会,但是实际上不行,不能保留。
**题目描述**
给定 $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$ 的商品都可以放在这里。我们将这些商品加入候选池。
1. **无差异的灵活性**:对于此时存在于候选池中的任意商品,因为它们的 $d_i \ge j$,它们显然也满足 $d_i > j-1$。这意味着,**候选池中的任何商品对于更早的位置(**$1$ **到** $j-1$**)都是绝对合法的**。因此,在当前位置做选择时,我们不需要担心某个商品是否必须留给前面的特定位置,它们的灵活性是完全等价的。
1. **贪心选择**:
- 如果当前位置 $j$ 是**折扣位**(即 $j \pmod{X+1} == 0$),为了让利润最大化,我们应该从候选池中挑出价格**最大**的商品用于打折。
- 如果当前位置 $j$ 是**全价位**,我们无法从该位置获得利润,为了把更高价格的商品保留给前面的折扣位,我们应该从候选池中挑出价格**最小**的商品消耗掉。
### 代码实现 (Code Implementation)
```cpp
#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)$ 的时间查找到在特定位置新解锁的商品。
1. **贪心维护**:使用 `std::multiset<long long>` 来作为可用商品的动态候选池。外层循环从 $N$ 倒序遍历至 $1$。每次到达一个新的位置 $j$,我们将 `add_at[j]` 中的元素全部加入池中。
1. **利润计算**:根据取模逻辑判断当前轮次,折扣直接加到 `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 是激活时间**。
```cpp
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](https://codeforces.com/gym/106416/submission/368218310)
::: 源代码
```cpp
/**
* 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……)