题目出自 Codeforces Round #126 (Div. 2) 的E。
题意大致如下：给定a，b，c，s，求三个非负整数x，y，z，满足0<=x<=y<=z，ax+by+cz=s，使得f(x,y,z)=|ax-by|+|by-cz|最小
思路：枚举z，得到一个方程ax+by=s-cz，用扩展欧几里得求出这个方程的一个解，然后三分通解的整系数，求出最小f值。至于为什么可以三分画画图就清楚了，两个绝对值函数叠加在一起最多只有三种状态(第一维表示临界点较小的那个绝对值函数)：(降,降)，(升,降)，(升,升)，无论两个函数哪个变化快，最终趋势都是：降然后升(由于临界点的情况不同，可能变成了单调的，但并不影响我们用三分求解)。
思来想去，决定搞一个三分的框架来避免头疼的临界问题（这是求最小值，求最大值时只需把<=换成>=即可，另外函数值在一段范围内不发生变化可能导致结果出错）：
|
1
2
3
4
5
6
7
|
int L = ..., R = ...;
while (L < R) {
int M1 = L + (R - L) / 3, M2 = R - (R - L) / 3;
if (F(M1) <= F(M2)) R = M2 - 1;
else L = M1 + 1;
} solve(L); |
出while循环后 L=R=目标解
下面是题目的源码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
/* ******************************************************************************** */#include <iostream> //#include <cstdio> //#include <cmath> //#include <cstdlib> //#include <cstring> //#include <vector> //#include <ctime> //#include <deque> //#include <queue> //#include <algorithm> //#include <map> //#include <cmath> //using namespace std; //
//
#define pb push_back //#define mp make_pair //#define X first //#define Y second //#define all(a) (a).begin(), (a).end() //#define fillchar(a, x) memset(a, x, sizeof(a)) // //
typedef pair<int, int> pii; //
typedef long long ll; //
typedef unsigned long long ull; //
//
#ifndef ONLINE_JUDGE //void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);} //
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R> //
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1; //
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T> //
void print(const T t){cout<<t<<endl;}template<typename F,typename...R> //
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T> //
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;} //
#endif // ONLINE_JUDGE //template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);} //
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);} //
template<typename T> //
void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];} //
template<typename T> //
void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];} //
//
const double PI = acos(-1.0); //
const int INF = 1e9 + 7; //
//
/* -------------------------------------------------------------------------------- */ll x, y, z, a, b, c, a0, b0;ll gcd(ll a, ll b) { return b? gcd(b, a % b) : a;
}void gcd(ll a, ll b, ll &d, ll &x, ll &y) {
if (!b) {
d = a; x = 1; y = 0;
}
else {
gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}ll f(ll k) { ll xx = x + k * b0, yy = y - k * a0;
return abs(xx * a - yy * b) + abs(yy * b - z * c);
}bool chk(ll k1, ll k2) {
if (x + k1 * b0 < 0) return false;
if (x + k1 * b0 > z) return true;
if (y - k1 * a0 < 0) return true;
if (y - k1 * a0 > z) return false;
if (x + k2 * b0 < 0) return false;
if (x + k2 * b0 > z) return true;
if (y - k2 * a0 < 0) return true;
if (y - k2 * a0 > z) return false;
if (x + k1 * b0 > y - k1 * a0) return true;
if (x + k2 * b0 > y - k2 * a0) return true;
return f(k1) <= f(k2);
}int main() {
#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE int n, s;
cin >> n >> s;
int cnt[3] = {};
for (int i = 0; i < n; i ++) {
int x;
scanf("%d", &x);
cnt[x - 3] ++;
}
a = cnt[0], b = cnt[1], c = cnt[2];
ll ans = INF, ix, iy, iz;
for (z = 1; z * c <= s; z ++) {
ll g;
gcd(a, b, g, x, y);
if ((s - z * c) % g) continue;
ll K = (s - z * c) / g;
x *= K;
y *= K;
a0 = a / g;
b0 = b / g;
ll L = -INF, R = INF;
while (L < R) {
ll M1 = L + (R - L) / 3, M2 = R - (R - L) / 3;
if (chk(M1, M2)) R = M2 - 1;
else L = M1 + 1;
}
ll xx = x + L * b0, yy = y - L * a0;
if (0 <= xx && xx <= yy && yy <= z) {
if (umin(ans, f(L))) {
ix = xx;
iy = yy;
iz = z;
}
}
}
if (ans < INF) cout << ix << " " << iy << " " << iz << endl;
else puts("-1");
return 0;
}/* ******************************************************************************** */ |