AtCoder Beginner Contest 374 (E + F)

AtCoder Beginner Contest 374

E

对于机器 $s$ 和机器 $t$ , 二分过程检查每一项工艺的过程中。

一定有一个机器的生产数量 $<A\times B$ 。

假设两台都 $\ge A\times B$ ,因为贵的那台机器这样生产总能被便宜的那台替换, 就与假设矛盾。

#include<bits/stdc++.h>
using namespace std;
#define int long longint n, x;
struct node{int a, p, b, q;
}v[110];bool check(int mid){int res = 0;for(int i = 1; i <= n; i ++){auto &[a, p, b, q] = v[i];int mn = 1e9;// 枚举 s < a * bfor(int j = 0; ; j ++){if(j * a >= a * b) break;mn = min(mn, j * p + (j * a > mid ? 0 : (mid - j * a + b - 1) / b * q));}// 枚举 t < a * bfor(int j = 0; ; j ++){if(j * b >= a * b) break;mn = min(mn, j * q + (j * b > mid ? 0 : (mid - j * b + a - 1) / a * p));}res += mn;}return res <= x;
}void solve(){cin >> n >> x;for(int i = 1; i <= n; i ++){int a, p, b, q;cin >> a >> p >> b >> q;v[i] = {a, p, b, q};}int l = 0, r = 1e9;while(l < r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}cout << l << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}

F

• Hint1

思考 shipment 的时间。

考虑到，订单一定要按顺序发出。（不太好严格证明这一点）

思考订单何时会发出 ？

所有的 $T_i$ 时间都有可能发出。

可能 $T_i$ 发出，当然也可能 $T_i+x$ 发出。

如此递推，$T_i+kx$ 就是可能的发出时间。其中，$k<=n-1$

因为第一次一定是某个订单准备好之后发出。

这样，我们要思考的发货时间就只有 $O(n^2)$ 个了。

原本有 $10^{12}$ 个。

• Hint2

考虑 $dp$ 求解。设 $f_{i,j}$ 表示考虑到 $i$ 个时间点，上次运走的最后一个订单是 $j$ , 不满意度之和的最小值。

那么来到 $f_{i,j}$ 之后如何转移呢 ?

可以什么都不做，$f_{i+1,j}\leftarrow f_{i,j}$ 。

可以考虑运走 $m$ 个订单，也就是运走 $[j+1,j+m]$ 这些订单。

那我们找到下一个最早的运货时间点满足 $cl{k}_d\ge T_{j+m}$ 并且 $cl{k}_d\ge cl{k}_i+x$。

$f_{d,j+m}\leftarrow f_{i,j}+{\sum }_{l=j+1}^{j+m}(T_d-T_l)$ 。

• Hint3

这个可以不看。因为我初始化错了，多写了一个多小时，所以写一下。

注意直接初始化 $f_{0,0}=0$ 即可。

我写了一个很不对的初始化 :

 初始化 f[1]f[1][0] = 0;for(int j = 1; j <= n; j ++){f[1][j] = clk[1] >= T[j] ? clk[1] - T[j] : 4e18;}

参考代码 :

void solve(){int n, k, x;cin >> n >> k >> x;vector<int> clk, T(n + 1, 0), sT(n + 1, 0);for(int i = 1; i <= n; i ++){cin >> T[i];sT[i] = sT[i - 1] + T[i];}clk.push_back(0); // presonal habitsfor(int i = 1; i <= n; i ++){for(int j = 0; j < n; j ++){clk.push_back(T[i] + j * x);}}sort(clk.begin(), clk.end());int sz = unique(clk.begin(), clk.end()) - clk.begin() - 1;vector<vector<int> > f(sz + 1, vector<int> (n + 1, 4e18));f[0][0] = 0;for(int i = 0; i < sz; i ++){for(int j = 0; j <= n; j ++){if(f[i][j] >= 4e18) continue ; // invalid statef[i + 1][j] = min(f[i + 1][j], f[i][j]); // do nothing // ship m ordersfor(int m = 1; m <= k && j + m <= n; m ++){int p = lower_bound(clk.begin(), clk.begin() + sz + 1, max(T[j + m], (j == 0 ? 0 : clk[i] + x))) - clk.begin();if(p == sz + 1) continue ; f[p][j + m] = min(f[p][j + m], f[i][j] + clk[p] * m - (sT[j + m] - sT[j]));}}}cout << f[sz][n] << '\n'; 
}