题解 | 牛客练习赛99 - B 物流
物流
https://ac.nowcoder.com/acm/contest/34330/B
写一个容易理解的B题吧：
首先，我们假设从A地向C地运输x吨货物，那么A向D运输A-x吨，B向C运输C-x吨，B向D运输B-(C-x)吨。记A->C的花费为ac，B->C的花费为bc，A->D的花费为ad，B->D的花费为bd。由此我们可以得到关于cost的一次函数：
y = (ac-ad+bd-bc)*x + bc*C+ad*A+bd*B-bd*C
可以看出y只和x的取值有关，我们可以分类讨论一下x的系数：
当(ac-ad+bd-bc) >= 0时，我们希望x越小越好，即A向C运输的量越小越好，那么B向C运输的量越大越好。
如果B>=C，那么我们直接将B全部运给C直至C满足要求，此时A向C运输0吨；如果B<C那么我们需要从A补充C-B吨：
即 x = 0 (B >= C), x = C - B (B < C)
当(ac-ad+bd-bc) < 0时，我们希望x越大越好，即A向C运输的量越大越好。
如果A>=C，那么我们直接将A全部运给C直至C满足要求，此时A向C运输C吨；如果A<C那么我们将可用的A全部运给C：
即 x = C (A >= C), x = A (A < C)
code如下：
/* 你将不再是道具，而是成为人如其名的人 --《Violet Evergarden》 */
#include <bits/stdc++.h>
#pragma GCC optimize(2, "Ofast", "inline")
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn (signed)(5e6 + 10)
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ri register
#define il inline
#define fi first
#define se second
#define pii pair<int, int>
#define sg signed
#define endl '\n'
#define spc ' '
#define M 998244353
#define inf 0x3f3f3f3f
#define lnf 0x3f3f3f3f3f3f3f3f
#define ninf -0x3f3f3f3f
#define readin(i, n, v) for(int o = (i); o < (n) + (i); o ++ ) cin >> (v)[o];
#define wtline(i, n, v) for(int o = (i); o < (n) + (i); o ++ ) cout << (v)[o] << " \n"[o == (n) + (i) - 1];
#define yon(x) cout << ((x) ? "Yes" : "No") << endl;
#define int128 __int128
#define gcd __gcd
int fpow(int a, int b) { int t = 1; for (; b; ) { if (b & 1) t *= a; b >>= 1; a *= a; } return t; }
int fpowm(int a, int b) { int t = 1; for (; b; ) { if (b & 1) t = t * a % M; b >>= 1; a = a * a % M; } return t; }
using namespace std;
/*
A->C X
ac*(x) + bc(C - x) + ad(A - x) + bd(B - C + x)
ac*x-bc*x-ad*x+bd*x+bc*C+ad*A+bd*B-bd*C
(ac-ad+bd-bc)*x +bc*C+ad*A+bd*B-bd*C
C接受A x, 接受 B C-x
d A-x B-C+X
*/
void solve() {
int A, B, C, D;
cin >> A >> B >> C >> D;
int ac, ad, bc, bd;
cin >> ac >> ad >> bc >> bd;
if((ac-ad+bd-bc) >= 0) {
if(B>=C) {
cout << (ac-ad+bd-bc)*0+bc*C+ad*A+bd*B-bd*C << endl;
}else {
cout << (ac-ad+bd-bc)*(C-B)+bc*C+ad*A+bd*B-bd*C << endl;
}
}else {
if(A >= C) {
cout << (ac-ad+bd-bc)*C+bc*C+ad*A+bd*B-bd*C << endl;
}else {
cout << (ac-ad+bd-bc)*A+bc*C+ad*A+bd*B-bd*C << endl;
}
}
}
sg main() {
IO;
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
查看12道真题和解析
