DDOSvoid's Blog

2021杭电多校10 J Pty plays game

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7086

简要题意：$Alice$​​​ 和 $Bob$​​​ 在进行一个游戏，$Alice$​​​ 有 $n$​​​ 个小精灵，$Bob$​​​ 有 $m$​​​ 个小精灵，每个小精灵有两个属性攻击力 $d$​​​ 和生命值 $h$​​​，一个攻击力为 $d_1$​​，生命值为 $h_1$​​ 的小精灵和一个攻击力为 $d_2$​​，生命值为 $h_2$​​ 的小精灵进行对战时间是 $t=min\lbrace \frac{h_1}{d_2}\frac{h_2}{d_1}\rbrace$​​​​，双方造成的伤害为 $t\times d_1$​ 和 $t\times d_2$​​​，现在双方的小精灵都按照给定的顺序排好，依次进行对战，胜利的小精灵将于失败方的下一个小精灵继续对战，每个小精灵的攻击和生命以 $ax+b$​ 的形式给出，现在请你确定最小的 $x\in[0,10^{18}]$，使得 $Alice$​ 可以获胜

$n,m\le 10^5$

Solution

我们尝试将小精灵的两个维度变成一个，我们令其为 $h\times d$

能够发现失败方的小精灵对胜利方的小精灵造成的伤害乘上胜利方的小精灵的攻击力恰好为失败方的小精灵的生命值乘上攻击力

也就是说我们只需要比较所有小精灵的生命值乘上攻击力的总和即可，与顺序无关

也就是说我们只需要求一个二次函数大于零的位置即可，为了避免浮点数运算，我们可以使用二分

时间复杂度 $O(n\log n)$，代码是队友写的

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
#include<bits/stdc++.h>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
typedef long long ll;
const ll inf=1e18;
struct node{
    ll a,b,c;
    node() {}
    node(ll _a,ll _b,ll _c) {a=_a,b=_b,c=_c;}
    friend node operator +(node x,node y){
        return node(x.a+y.a,x.b+y.b,x.c+y.c);
    }
    friend node operator -(node x,node y){
        return node(x.a-y.a,x.b-y.b,x.c-y.c);
    }
    __int128 f(ll x){
        return (__int128)a*x*x+(__int128)b*x+c;
    } 
    ll get(){
        if(c>0) return 0;
        if(!a){
            if(b<=0) return inf+1;
            return -c/b+1;
        }
        ll p=-b/(2*a),ans=inf+1;
        if(a<0){
            if(b<=0) return inf+1;
            if(f(p+1)>0) ans=min(ans,p+1);
            ll l=1,r=p;
            for(;l+1<r;){
                ll mid=l+r>>1;
                f(mid)>0?r=mid:l=mid;
            }
            if(f(l)>0) r=l;
            if(f(r)>0) ans=min(ans,r);
            return ans;
        }
        else{
            ll l=1,r=inf+1;
            for(;l+1<r;){
                ll mid=l+r>>1;
                f(mid)>0?r=mid:l=mid;
            }
            if(f(l)>0) r=l;
            return r;
        }
    }
}A,B;
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    for(;T--;){
        int n,m;
        cin>>n>>m;
        A=B=node();
        fo(i,1,n){
            ll h,_h,d,_d;
            cin>>h>>_h>>d>>_d;
            A=A+node(_h*_d,h*_d+_h*d,h*d);
        }
        fo(i,1,m){
            ll h,_h,d,_d;
            cin>>h>>_h>>d>>_d;
            B=B+node(_h*_d,h*_d+_h*d,h*d);
        }
        node C=A-B;
        ll ans=C.get();
        ans>inf?cout<<"none\n":cout<<ans<<"\n";
    }
}