题解：AT_abc374_e [ABC374E] Sensor Optimization Dilemma 2

Binah_cyc · 2024-10-07 15:04:46 · 题解

本文给出一个看似是乱搞的正解并且给出了证明。

做法：

本题二分显然，二分每一个步骤需要达到的生产力，然后考虑对二分出的答案进行判断。

判断时考虑贪心，对于每一个步骤，性价比更劣的那一台机器我们最多使用 100 台，这样跑的飞快，并且是正确的。

示例代码：

// Problem: E - Sensor Optimization Dilemma 2
// Contest: AtCoder - KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374）
// URL: https://atcoder.jp/contests/abc374/tasks/abc374_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,X;
struct Node
{
    pair<int,int> a,b;
}x[105];

int work(int k,int mid)
{
    int cnt=INT_MAX;
    for(int i=0;i<=100;i++)
        cnt=min(cnt,x[k].b.second*i+(mid-x[k].b.first*i+x[k].a.first-1)/x[k].a.first*x[k].a.second);
    //枚举机器b使用多少个，快速计算总答案
    return cnt;
}
bool check(int mid)
{
    int cnt=0;
    for(int i=1;i<=n;i++) cnt+=work(i,mid);
    return cnt<=X;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>X;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i].a.first>>x[i].a.second>>x[i].b.first>>x[i].b.second;
        if(1.0*x[i].a.second/x[i].a.first>1.0*x[i].b.second/x[i].b.first) swap(x[i].a,x[i].b);//钦定机器a是性价比更高的机器
    }
    int l=0,r=1e9,ans;//能达到的最大生产力为1e9
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}

证明

对于每一个步骤，我们设该步骤使用了 x 台 A 机器与 y 台 B 机器，二分出来的最低生产力要求为 k，显然，有 Ax+By \ge k。

因为 A,B \le 100，所以 Ax+By-k \le 100，设它等于 c。

现在，我们假设先全都使用机器 A，我们可以得到 c_0，然后减少 1 个 A 机器的数量，并使用 B 机器代替它，就可以得到 c_1，再减少一个 A 并使用 B 代替它，得到 c_2，等等。

因为 c 只有 100 个取值，所以它在 100 以内必定存在循环节。考虑到这里，结论也就呼之欲出了。