题解 P6784 【「EZEC-3」造房子】

Daidly · 2020-08-24 17:47:07 · 题解

先分析一下题意：

想法：

• 先把剩余的c个替补材料给换成A材料和B材料，使得A材料和B材料的个数最接近。

• 然后模拟一下盖房子的过程，第n次减n就行了。

实践：

• 先分别判断A材料和B材料和c的大小关系：

  $2.$ 如果$a<b$，并且$c$足够填满$a<b$这个坑，那就`c-=b-a,a=b`；要是$c$填不满，那就`a+=c,c=0`。 $3.$ 如果$a=b$，那就不用管。

• 然后再把剩余的c平均分配给a和b。

• 最后，一个for(long long i=1;i<=min(a,b);i++)循环，每次减i，判断a和b是否小于i，也就是不能减了，就够了。

• 在这里补充一点如果数据存在a或b等于零的话，就要特判一下，例如10 0 0。

#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
int main(){
    cin>>a>>b>>c;
   if(a==0||b==0){cout<<"0";return 0;}//特殊判断一下
    if(a>b){
        if(a-b>c){
            b+=c,c=0;
        }else{
            c-=a-b,b=a;
        }
    }
    if(a<b){
        if(b-a>c){
            a+=c,c=0;
        }else{
            c-=b-a,a=b;
        }
    }
    a+=c/2;b+=c/2;
    for(long long i=1;i<=max(a,b);i++){
        a-=i;b-=i;
        if(a<i||b<i){
            cout<<i;
            return 0;
        }
    }
}

当然，最后的循环的a和b改成a和b中较小的那个也行，如：

a=min(a,b)+c/2;
for(long long i=1;i<=min(a,b);i++){
    a-=i;
    if(a<i+1){
        cout<<i<<endl;
        return 0;
    }
}

但好像不会快多快。

好了，这道题的讲解就到此结束，谢谢大家。