[ICPC 2018 Jiaozuo Onsite B]Ultraman vs. Aodzilla and Bodzilla

Link

Solution

很不错的想法啊……
首先,一个结论是,1…n这些数字,取出一些,能凑出1…\frac {n(n+1)}{2}之间的所有的和。
S(x)是最小的满足\frac {n(n+1)}{2}\ge xn
那么,同时打掉两个怪物所需的最少时间是S(HP_A+HP_B),因为S(HP_A+HP_B)个轮次中可以凑出HP_A或者HP_B,这样其他的轮次用于打另一个怪,在这个时间内肯定可以打完。
枚举先打哪个怪物,所需的时间同样可以计算。设先打x后打y,那么最终的伤害就是S(HP_x)ATK_x+S(HP_A+HP_B)ATK_{y}。枚举一下先打A还是先打B,显然最小的伤害值一定在这两个中间产生,因为伤害值的表达式中的每一个系数都达到了最小值。
现在就考虑如何构造字典序最小的打法。
如果先打A,只有B不够打才需要修改。那么就从后往前找到第一个合法的位置把这一轮次的打A变成打B。这肯定是所有改法中字典序最小的,因为如果不改这个,就需要在前面改两个。同时,由一开始的那个结论,这样位置肯定是存在的。
如果先打B,那么为了让字典序最小,需要把一些尽量靠前的位置从B改成A。那就从前往后枚举,只要改了之后B还够打就改。最后唯一的可能是A还是不够打。那就把最后一个A的位置改回B,然后直接把A还缺的打击值的那一轮改成A。注意,A还缺的那一轮的打击值一定\le n_1,也就是一定是属于B的轮次。因为,即使是初始状态未做任何调整的前提下,A的打击值+n_1就一定> HP_A了。

Code

int Search(int x) {
    int L=1,R=x;
    while(L!=R) {
        long long M=(L+R)/2;
        if(M*(M+1)/2>=x)
            R=M;
        else
            L=M+1;
    }
    return L;
}

std::pair<long long,std::string> Case1(int ha,int hb,int aa,int ab) {
    long long n1=Search(ha),n=Search(ha+hb);
    long long hita=n1*(n1+1)/2,hitb=n*(n+1)/2-hita;
    long long harm=aa*n1+ab*n;
    std::string s;
    for(int i=1;i<=n1;++i)
        s+='A';
    for(int i=n1+1;i<=n;++i)
        s+='B';
    if(hitb<hb) {
        for(int i=n1;i>=1;--i) {
            if(hita-i>=ha && hitb+i>=hb) {
                s[i-1]='B';
                hita-=i;
                hitb+=i;
                break;
            }
        }
    }
    if(!(hita>=ha && hitb>=hb)) throw;
    return {harm,s};
}

std::pair<long long,std::string> Case2(int ha,int hb,int aa,int ab) {
    long long n1=Search(hb),n=Search(ha+hb);
    long long hitb=n1*(n1+1)/2,hita=n*(n+1)/2-hitb;
    long long harm=ab*n1+aa*n;
    std::string s;
    for(int i=1;i<=n1;++i)
        s+='B';
    for(int i=n1+1;i<=n;++i)
        s+='A';
    int last=0;
    for(int i=1;i<=n1;++i)
        if(hitb-i>=hb) {
            hitb-=i;
            hita+=i;
            s[i-1]='A';
            last=i;
        }
    if(hita<ha) {
        s[last-1]='B';
        s[last+ha-hita-1]='A';
        hitb-=ha-hita;
        hita=ha;
    }
    if(!(hita>=ha && hitb>=hb)) for(;;);
    return {harm,s};
}

void Work() {
    int ha,hb,aa,ab;std::cin>>ha>>hb>>aa>>ab;
    auto Ans=std::min(Case1(ha,hb,aa,ab),Case2(ha,hb,aa,ab));
    std::cout<<Ans.first<<' '<<Ans.second<<'\n';
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注