Znzryb's Blog
0%

AtCoder Beginner Contest 374 E - Sensor Optimization Dilemma 2

Posted on Edited on

AC代码与思路

相比于最后一次TLE背包提交，加了以下这些

1
for(int j=1;j<=x-sumYen;j++) {  // 背包容量为钱，背包价值为生产力
1
2
if(sumYen>x)
     return false;

主要思路是二分答案加背包dp

背包容量为钱，背包价值为能加工多少产品

通过背包dp让加工产品最大化

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e9)+7,MAXA=1e7+7;
int n,x,mach[MAXN][6];
int dp[MAXA];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        dp[0]=0;
        int cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        bool isBreak=false;
        if(sumYen>x)
            return false;
        for(int j=1;j<=x-sumYen;j++) {  // 背包容量为钱，背包价值为能加工多少产品
            int up1=j-p1,up2=j-p2;
            if(up1>=0)
                dp[j]=dp[up1]+cap1;
            if(up2>=0)
                dp[j]=max(dp[j],dp[up2]+cap2);
            if(dp[j]>=needCap) {
                sumYen+=j;isBreak=true;break;
            }
        }
        if(!isBreak)
            return false;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了
// 就TLE了3个点 https://atcoder.jp/contests/abc374/submissions/58545771
// AC https://atcoder.jp/contests/abc374/submissions/58545889
// AC https://www.luogu.com.cn/record/180827335

以下是错误提交记录与心路历程

这个程序实际上没啥太大问题，但是即便开long long minYen还是超范围溢出了。

这个题目再次证明了，二分的题目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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e13)+7;
ll n,x,mach[MAXN][6];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        ll minYen=0;ll needMach1=(needCap-1)/cap1+1,needMach2=(needCap-1)/cap2+1; // (a-1)/b +1
        minYen=needMach1*p1;          // 向上取整的trick
        minYen=min(minYen,needMach2*p2); 
        sumYen+=minYen;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 34 WA 64 https://atcoder.jp/contests/abc374/submissions/58535735

原来两台机子都能用！那check()函数写起来是比较麻烦

1
2
Both machines S_i and T_i can be used for process i.
If you purchase both machines S_i and T_i, the number of items that can be processed in process i will be the sum of the items processed by both machines.

AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537475

加上了对于组合的判定

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e10)+7;
ll n,x,mach[MAXN][6];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        ll minYen;ll needMach1=(needCap-1)/cap1+1,needMach2=(needCap-1)/cap2+1; // (a-1)/b +1
        minYen=min(needMach1*p1,needMach2*p2);
        ll firstMach1=needCap/cap1,remainMach2=(needCap-firstMach1*cap1-1)/cap2+1;
        ll priceComb1=firstMach1*p1+remainMach2*p2;
        ll firstMach2=needCap/cap2,remainMach1=(needCap-firstMach2*cap2-1)/cap1+1;
        ll priceComb2=firstMach2*p2+remainMach1*p1;;
        minYen=min(minYen,min(priceComb1,priceComb2));
        sumYen+=minYen;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了

我怀疑是我的向上取整模版的问题

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cmath>
using namespace std;
long long a=0;
int main()
{
    cout<<-1/782<<endl;
    std::cout << (0-1)/782+1 << std::endl;   // 模版行
    cout<<ceil(a/1.0/782)<<endl;
    return 0;
}
1
2
3
0
1
0

毫无疑问，0/782=0，你就算加ceil()也应该是0，但显然我们的模版出了问题。

哎，用系统ceil（）提交了一遍，发现又WA了，和前面一模一样，只能说就这样吧，累了。

https://atcoder.jp/contests/abc374/submissions/58539387

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e10)+7;
ll n,x,mach[MAXN][6];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        ll minYen;ll needMach1=ceil(needCap/1.0/cap1),needMach2=ceil(needCap/1.0/cap2); // (a-1)/b +1
        minYen=min(needMach1*p1,needMach2*p2);
        ll firstMach1=needCap/cap1,remainMach2=ceil((needCap-firstMach1*cap1)/1.0/cap2);
        ll priceComb1=firstMach1*p1+remainMach2*p2;
        ll firstMach2=needCap/cap2,remainMach1=ceil((needCap-firstMach2*cap2)/1.0/cap1);
        ll priceComb2=firstMach2*p2+remainMach1*p1;;
        minYen=min(minYen,min(priceComb1,priceComb2));
        sumYen+=minYen;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了

引入了性价比概念，但发现连样例都过不了😂，还是要用dp。

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e9)+7,MAXA=1e7+7;
ll n,x,mach[MAXN][6];
int dp[MAXA];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll sumCap=0,capA=mach[i][1],pA=mach[i][2],capB=mach[i][3],pB=mach[i][4];
        while (true) {
            if(sumCap>=needCap)
                break;
            ll remainCap=needCap-sumCap;
            double effA=pA*1.0/min(remainCap,capA);   // 采用A机器的零件均摊价格(总消耗钱数/每台机器能做的有贡献零件数)
            double effB=pB*1.0/min(remainCap,capB);   // 采用B机器零件均摊价格
            if(effA<effB)
                sumCap+=capA,sumYen+=pA;
            else
                sumCap+=capB,sumYen+=pB;
        }
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    // for(int i=1;i<=n;i++) {
    //     if(mach[i][2]/1.0/mach[i][1]>mach[i][4]/1.0/mach[i][3]) {
    //         swap(mach[i][1],mach[i][3]);
    //         swap(mach[i][2],mach[i][4]);
    //     }
    // }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

将中间的判定改为了背包dp，果然这种通用做法就是应用性广泛且经过证明
// 就TLE了3个点 https://atcoder.jp/contests/abc374/submissions/58545771

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e9)+7,MAXA=1e7+7;
int n,x,mach[MAXN][6];
int dp[MAXA];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        dp[0]=0;
        int cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        bool isBreak=false;
        if(sumYen>x)
            return false;
        for(int j=1;j<=x-sumYen;j++) {  // 背包容量为钱，背包价值为生产力
            dp[j]=0;
            int up1=j-p1,up2=j-p2;
            if(up1>=0)
                dp[j]=dp[up1]+cap1;
            if(up2>=0)
                dp[j]=max(dp[j],dp[up2]+cap2);
            if(dp[j]>=needCap) {
                sumYen+=j;isBreak=true;break;
            }
        }
        if(!isBreak)
            return false;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    // for(int i=1;i<=n;i++) {
    //     if(mach[i][2]/1.0/mach[i][1]>mach[i][4]/1.0/mach[i][3]) {
    //         swap(mach[i][1],mach[i][3]);
    //         swap(mach[i][2],mach[i][4]);
    //     }
    // }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了
// 就TLE了3个点 https://atcoder.jp/contests/abc374/submissions/58545771