ABC063

[ABC063C] Bugged

题面翻译

有 $N$ 道题，答对一道获得 $A_i$ 分，答错不得分。但是如果现在分数为 $10$ 的倍数将会显示 $0$ 分，问最高可以获得多少分？

题目描述

あなたはコンピュータで試験を受けています。試験は $ N $ 問の問題からなり、$ i $ 問目の問題の配点は $ s_i $ です。それぞれの問題に対するあなたの解答は「正解」または「不正解」のいずれかとして判定され、正解した問題の配点の合計があなたの成績となります。あなたが解答を終えると、解答がその場で採点されて成績が表示される…はずでした。

ところが、試験システムに欠陥があり、成績が $ 10 $ の倍数の場合は、画面上で成績が $ 0 $ と表示されてしまいます。それ以外の場合は、画面に正しい成績が表示されます。この状況で、成績として画面に表示されうる最大の値はいくつでしょうか？

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ s_1 $ $ s_2 $ $ : $ $ s_N $

输出格式

成績として画面に表示されうる最大の値を出力せよ。

样例 #1

样例输入 #1
3
5
10
15
样例输出 #1
25
样例 #2

样例输入 #2
3
10
10
15
样例输出 #2
35
样例 #3

样例输入 #3
3
10
20
30
样例输出 #3
0
提示

制約

入力値はすべて整数である。

$ 1 < = N < = 100 $

$ 1 < = s_i < = 100 $

Sample Explanation 1

$ 10 $ 点の問題と $ 15 $ 点の問題に正解し、$ 5 $ 点の問題には正解しないことで成績が $ 25 $ となり、この成績は画面に正しく表示されます。$ 5 $ 点の問題にも正解すると成績が $ 30 $ となりますが、この成績は画面上では $ 0 $ と表示されてしまいます。

Sample Explanation 2

すべての問題に正解すると成績が $ 35 $ となり、この成績は画面に正しく表示されます。

Sample Explanation 3

どのような解答状況でも成績は $ 10 $ の倍数となり、画面上では $ 0 $ と表示されてしまいます。

思路

比较容易想到的就是贪心：如果所有数字的和不是10的倍数，那么直接输出即可。但如果是10的整数倍，我们只有减去一个某一个数即可。

那么要减去谁呢？如果这个数是10的倍数，那么所有数之和减去该数后，还是10的整数倍，没有任何效果。

那么为了使得结果最大化，我们应该减去最小的、且不是10的整数倍的数。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int a[MAXN],f[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    int sum=0;
    int MIN=MAXN;
    int flag=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        //选出符合情况的最小值
        if(a[i]%10){
            MIN=min(MIN,a[i]);
            flag=1;
        }
    }
    //注意 可能选不出满足情况的最小值
    if(!flag)cout<<0;
    
    //本身和不是10的整数倍
    else if(sum%10)cout<<sum;
    
    //本身和是10的整数倍
    else cout<<sum-MIN;
    return 0;
}

[ABC063D] Widespread

题面翻译

你散步的时候，突然$N$个魔物出现了。

各个魔物都有体力这个值，第$i$个魔物出现时的体力是$h_i$,而体力$0$以下的魔物立即消失。

幸运的是，你是一个熟练的魔法师，可以发动爆炸来攻击魔物。一次爆炸可以减少魔物的体力，如下所示。

选择生存的魔物，以魔物为中心引起爆炸。成为爆炸中心的魔物的体力$A$减少，其他魔物的体力$B$分别减少。

这里需要说明的是，$A$和$B$是预先确定的值，且$A>B$。

为了消灭所有的魔物，你最少需要引起几次爆炸呢?

题目描述

あなたが散歩していると、突然 $ N $ 体の魔物が出現しました。それぞれの魔物は体力という値を持ち、$ i $ 体目の魔物の出現時の体力は $ h_i $ です。体力が $ 0 $ 以下となった魔物は直ちに消滅します。

幸い、あなたは熟練の魔法使いであり、爆発を引き起こして魔物を攻撃できます。一回の爆発では、以下のように魔物の体力を減らすことができます。

生存している魔物を一体選び、その魔物を中心に爆発を引き起こす。爆発の中心となる魔物の体力は $ A $ 減り、その他の魔物の体力はそれぞれ $ B $ 減る。ここで、$ A $ と $ B $ はあらかじめ定まった値であり、$ A > B $ である。

すべての魔物を消し去るためには、最小で何回の爆発を引き起こす必要があるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A $ $ B $ $ h_1 $ $ h_2 $ $ : $ $ h_N $

输出格式

すべての魔物を消し去るために必要な最小の爆発の回数を出力せよ。

样例 #1

样例输入 #1
4 5 3
8
7
4
2
样例输出 #1
2
样例 #2

样例输入 #2
2 10 4
20
20
样例输出 #2
4
样例 #3

样例输入 #3
5 2 1
900000000
900000000
1000000000
1000000000
1000000000
样例输出 #3
800000000
提示

制約

入力値はすべて整数である。

$ 1 < = N < = 10^5 $

$ 1 < = B < A < = 10^9 $

$ 1 < = h_i < = 10^9 $

Sample Explanation 1

以下のようにして、$ 2 $ 回の爆発ですべての魔物を消し去ることができます。 - まず、体力が $ 8 $ の魔物を中心に爆発を引き起こす。$ 4 $ 体の魔物の体力はそれぞれ $ 3 $, $ 4 $, $ 1 $, $ -1 $ となり、最後の魔物は消滅する。 - 次に、残りの体力が $ 4 $ の魔物を中心に爆発を引き起こす。残っていた $ 3 $ 体の魔物の体力はそれぞれ $ 0 $, $ -1 $, $ -2 $ となり、すべての魔物が消滅する。

Sample Explanation 2

それぞれの魔物を中心に $ 2 $ 回ずつ、合計で $ 4 $ 回の爆発を引き起こす必要があります。

思路

思考，可以发现存在明显的分界点情况，在某一个临界次数值下，可以消灭全部怪物，具有单调性，所以可以考虑二分。

这里根据题目要求，二分的是次数。重心放在check函数怎么写。

不难想到使用贪心的思想，对于一个怪物来说，如果你能使用伤害为b的攻击，将其消灭，则使用b。

否则就只能使用爆炸了，统计一下爆炸的次数，然后和mid比较即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll h[MAXN],n,a,b;

//用来解决取整问题
ll Ceil(ll x,ll y){
    if(x%y==0)return x/y;
    else return x/y+1;
}
bool check(ll mid){
    ll cnt=0;
    for(ll i=1;i<=n;i++){
        if(h[i]<=mid*b)continue;
        cnt+=Ceil(h[i]-mid*b,a-b);
    }
    //比较爆炸次数cnt和mid的值
    return cnt<=mid;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    cin>>a>>b;
    ll MAX=0;
    for(ll i=1;i<=n;i++)cin>>h[i],MAX=max(MAX,h[i]);
    ll l=0,r=Ceil(MAX,b);
    while(l+1<r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            r=mid;
        }
        else l=mid+1;
    }
    if(check(l))cout<<l;
    else cout<<l+1;
    return 0;
}