Codeforces Round #491 (Div. 2)题解

题目链接:Codeforces Round #491 (Div. 2)

A. If at first you don’t succeed…

题目类型: 容斥
题意:
题目大意是要进行一次考试,有人考好了有人没考好,考好的人都会去餐馆吃饭,餐馆有两个,有A个人去了第一个餐馆,有B个人去了第二个餐馆,有C个人两个餐馆都去了,现在问有多少人没有考好.
样例给出是给出了A,B,C,N的值,如果合法就输出没考好的人数,不合法就输出-1.
思路:
根据容斥原理,设去第一个餐馆的人的集合为 A ,去第二个餐馆的人数集合为 B ,两个都去的集合为 C ,那么只去了A餐馆的人数是 A C ,只去了B餐馆的人数是 B C ,哪里都没去的是: N ( ( A C ) + ( B C ) + C ) ,做的时候注意判断A-CB-C是否合法
代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // freopen("in.txt", "r", stdin);
    int a, b, c, n;
    cin >> a >> b >> c >> n;
    int ans1 = a - c;
    int ans2 = b - c;
    if (ans1 < 0 || ans2 < 0)
    {
        cout << -1 << endl;
        return 0;
    }
    int ans = n - ans1 - ans2 - c;
    if (ans > 0)
        cout << ans << endl;
    else
        cout << -1 << endl;

    return 0;
}

B. Getting an A

题目类型:贪心
题意:
俄罗斯对每个学生的考试成绩打分等级是1~5分,5分为最高分,一个学生的最终成绩为它的所有科目的总分除以科目数量。给出一个数n,代表有几门课,然后给出老师对这些课的打分,现在这个学生想获得5分,问他至少需要重新考试几门才可以获得最后的分数为5分(假设他重新考试分数一定为5分)
思路:
按照分数从小到大排序,然后依次修改分数,计算次数,知道最后的分数为5分为止
代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
double a[N];
int n;
int judge()
{
    double sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
    }
    int ans = (int)(sum / (n * 1.0) + 0.5);
    return ans >= 5;
}
int main()
{

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lf", &a[i]);
    }
    sort(a, a + n);
    if (judge())
    {
        printf("0\n");
    }
    else
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            a[i] = 5.0;
            cnt++;
            if (judge())
            {
                printf("%d\n", cnt);
                break;
            }
        }
    }

    return 0;
}

C. Candies

题目类型:二分
题意:
是有n个糖果,第一个人每天早上吃k个(如果剩余糖果数量小于k个则直接吃完),第二个人每天晚上吃剩余糖果总数的10%,现在题目让你求出一个最小的k,可以让这些糖果吃完的时候,第一个人可以吃糖果总数的一半及以上。
思路:
我们模拟吃糖果的过程并且二分答案,注意一下奇数的情况.,这题需要开long long
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll judge(ll m)
{
    ll nn = n, cnt = 0;
    while (nn > 0)
    {
        cnt += min(nn, m);
        nn -= m;
        nn -= nn / 10;
    }
    return cnt >= (n + 1) / 2;
}
int main()
{
    scanf("%lld", &n);
    ll l = 1, r = n;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (judge(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}

未完待续..

相关文章
相关标签/搜索