AtCoder Beginner Contest 338 C - Leftover Recipes 题解

前言

场上刚开始还天真的以为是个爆搜或者奇怪的背包，浪费了好久。。

思路

看到这个题我们首先想到的一定是暴力 dfs 枚举做菜品 a 还是菜品 b，但复杂度为 O(2ans)\mathcal O(2^{ans})，显然无法通过本题。于是我们来思考一下贪心做法。

实际上，这道题的题意可以简化成 nn 个不等式，设我们最后做了 xx 道菜品 a，yy 道菜品 b，就可以表示成如下形式：

a1x+b1y≤q2,a2x+b2y≤q2,⋯ ,anx+bny≤qna_1x+b_1y\leq q_2,a_2x+b_2y\leq q_2,\cdots,a_nx+b_ny\leq q_n

并且注意到题意里 a,b,qa,b,q 的取值范围都不超过 10610^6，于是我们可以考虑枚举当前的 xx 或 yy（这里选择枚举 yy），对不等式做变形，得到如下式子：

x≤⌊qi−biyiai⌋(1≤i≤n,biyi≤qi)x\leq \lfloor \frac{q_i-b_iy_i}{a_i} \rfloor(1\leq i\leq n,b_iy_i\leq q_i)

按照以上思路，枚举 yy 并且按上式求出最大并且对于每一个 qi,ai,biq_i,a_i,b_i 都合法的 xx 即可，时间复杂度 O(kn)\mathcal O(kn)，其中 kk 是最后的答案，而答案不超过 10610^6，可以通过本题。

同时要注意判断当前 yy 是否合法以及特判 ai=0a_i=0 的情况。

代码

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
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mp_ make_pair
#define pb_ push_back
#define pob_ pop_back
#define fst first
#define snd second
#define debug cout<<"********\n";
#define reset(x,y) memset(x,y,sizeof(x))
#define fi(x) freopen(x,"r",stdin)
#define fo(x) freopen(x,"w",stdout)
#define iosf ios::sync_with_stdio(0);cin.tie(0);
#define prec(x) cout<<setprecision(x);
#define prec0(x) cout<<fixed<<setprecision(x);
#define s(x,y) x[y-1]
#define Misaka16172 sb

using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;

template <class T>
inline void read(T &x){
    x = 0;T w = 1;
    char c = 0;
    while(c<'0' || c>'9'){
        if(c=='-')	w = -1;
        c = getchar();
    }
    while(c>='0' && c<='9'){
        x = ((x<<3)+(x<<1))+c-'0';
        c = getchar();
    }
    x = x*w;
}
int n;
ll q[15],a[15],b[15];
ll ans = 0;

void solve(){
    read(n);
    for(int i=1;i<=n;i++)	read(q[i]);
    for(int i=1;i<=n;i++)	read(a[i]);
    for(int i=1;i<=n;i++)	read(b[i]);
    for(int y=0;y<=1e6;y++){
        bool flag = 0;
        for(int i=1;i<=n;i++){
            if(y*b[i]>q[i]){	//检查当前y是否合法，不合法直接退出
                flag = 1;
                break;
            }
        }
        if(flag)	break;
        ll x = INF;
        for(int i=1;i<=n;i++){
            if(a[i]>0)	x = fmin(x,floor(q[i]-b[i]*y)*1.0/a[i]);	//求出最大的且满足要求的x
        }
        if(x>=0)	ans = fmax(ans,x+y);	//更新答案
    }
    cout<<ans;
}    

int main(){
    int t = 1;
//    read(t);
    for(int tt=1;tt<=t;tt++){
        solve();
    }
}