Codeforces Round #601 (Div. 2)

A - Changing Volume

题意：有个遥控器，有+1-1+2-2+5-5，6个键，不允许把音量调整至负数（当音量<5，则无法按-5），求最少按键使得a变成b。

题解：一开始以为音量<5按-5会变成0，这样要多一个特判。由于给的数字的缘故，并不会有穿过去然后反过来减掉更优的，比如+4不需要+5-1，直接+2+2。所以直接模拟。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void test_case() {
    int a, b;
    scanf("%d%d", &a, &b);
    if(a > b)
        swap(a, b);
    printf("%d\n", (b - a) / 5 + ((b - a) % 5 + 1) / 2);
}

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int t = 1;
    scanf("%d", &t);
    for(int ti = 1; ti <= t; ++ti) {
        //printf("Case #%d: ", ti);
        test_case();
    }
}

B - Fridge Lockers

题意：有个n点m边无向图，每个点是冰箱，每条边是一种锁，要求安排一种方法使得每个点的锁不被另一个点的锁覆盖。

题解：原本m可以>n，这题就很复杂了，应该就把多出来的边换掉一最昂贵的边，意思是取出目前最贵的一组(u,v)，然后连边(x,u)，(x,v)，这样就消费掉1条边且只增加了2x，当x取最小值时，比每次取出最小的(x,y)增加的x+y要便宜。但是这样贪心是不是有漏洞就不得而知了。现在规定m<=n，很显然不被另一个锁覆盖的意思就是要连至少两条边，且两条边连去不同的点。这样有解的时候当n>2且m=n时，方法是连成一个环。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void test_case() {
    int n, m;
    scanf("%d%d", &n, &m);
    bool suc = (m == n && n > 2);
    int sum = 0;
    for(int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        sum += x;
    }
    if(!suc) {
        puts("-1");
        return;
    }
    printf("%d\n", 2 * sum);
    for(int i = 1; i <= n - 1; ++i)
        printf("%d %d\n", i, i + 1);
    printf("%d %d\n", n, 1);
}

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int t = 1;
    scanf("%d", &t);
    for(int ti = 1; ti <= t; ++ti) {
        //printf("Case #%d: ", ti);
        test_case();
    }
}