Codeforces Round #415 (Div. 2)

题面：https://codeforces.com/contest/810/problems

A. Straight «A»

题意

给定$n$和$k$，分别表示现有的成绩个数和满分。问现在最少还需要多少个成绩才能使平均分四舍五入后等于满分。

解法

数据范围小，不停的加满分。随便模拟一下就好了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, sum = 0, cnt = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        sum += t;
    }
    while(2 * sum < (2 * k - 1) * n)
    {
        sum += k;
        n++;
        cnt++;
    }
    return 0;
}

B. Summer sell-off

题意

商店卖商品，知道每天有多少顾客来买和每天的商品个数。店主决定选$f$天sell-out，这一天商品个数会加倍。问怎么选能够卖出最多的商品。

解法

贪心就好了呀。
排个序，按照加倍前后多卖出的商品个数，然后取一取就可以了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
struct node{
    ll l, r;
};
node a[maxn];
bool cmp(const node & pa, const node & pb)
{
    ll a = min(2 * pa.l, pa.r) - min(pa.l, pa.r);
    ll b = min(2 * pb.l, pb.r) - min(pb.l, pb.r);
    return a > b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, f, ans = 0;
    cin >> n >> f;
    for(int i = 0; i < n; i++)
        cin >> a[i].l >> a[i].r;
    sort(a, a + n, cmp);
    for(int i = 0; i < f; i++)
        ans += min(2 * a[i].l, a[i].r);
    for(int i = f; i < n; i++)
        ans += min(a[i].l, a[i].r);
    cout << ans << endl;
    return 0;
}

C. Do you want a date?

题意

给定一个$n(n < 3 \cdot 10^5)$个数的集合，设$a$为这个集合的子集,令$F(a)=max|a_i-a_j|(i, j \in a)$。求所有子集的$F$值和。

解法

看到这题，首先会想到是排个序。然后枚举最大和最小的两个数，中间的数可以取或不取算一下排列数再累加。但这样的话复杂度是$n^2$的显然不能通过测评。
所以考虑优化，用前缀和来做。
分别考虑每个加$2^0, 2^1, 2^2…., 2^n-2$的数
比如$2^0$: $a_2-a_1, a_3-a_2,….a_n-a_{n-1}$然后加起来发现是$s_n-s_{n-1}-a_1$
得到结论对于$2^i$为$s_n-s_{i+1}-s_{n-i-1}$
记录一下2的幂取模的结果就好了。

当然还可以找规律~~开始找规律~~
考虑5个数的子集
要加的内容为：

$a_2-a_1, (a_3-a_1)\cdot2, (a_4-a_1) \cdot 2^2, (a_5-a_1) \cdot 2^3$
$a_3-a_2, (a_4-a_2)\cdot2, (a_5-a_2)\cdot2^2$
$a_4-a_3, (a_5-a_3)\cdot2$
$a_5-a_4$

把上面这一堆加起来后会得到：
$F(a) =15a_5+6a_4-6a_4-15a_1\\=(1-16)a_5+(8-2)a_4+(4-4)a_3+(2-8)a_4+(1-15)a_1$
喜闻乐见找规律

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
ll a[maxn], bit[maxn];
ll sum[maxn], ans;
void solve1(int n)
{
    for(int i = 1; i <= n; i++)
    {
        ans += (bit[i - 1] + mod - bit[n - i]) % mod * a[i];
        ans %= mod;
    }
    cout << ans << endl;
}
void solve2(int n)
{
    for(int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        sum[i] %= mod;
    }
    for(int i = 0; i <= n - 1; i++)
    {
        ll add = sum[n] + 2 * mod - sum[n - i - 1] - sum[i + 1];
        add %= mod;
        add *= bit[i];
        add %= mod;
        ans += add;
        ans %= mod;
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    bit[0] = 1;
    for(int i = 1; i <= n; i++)
        bit[i] = bit[i - 1] * 2 % mod;
    solve1(n);
    //solve2(n);
    return 0;
}