Codeforces Round #446 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #446 (Div. 2)
过题数：3
排名：798/10599

A. Greed

题意

有 $n$ 个可乐罐，第 $i$ 个可乐罐的容量为 $b_i$，其中剩余的可乐体积为 $a_i$，问能否将所有可乐罐中剩余的可乐都倒到两个可乐罐中。

输入

第一行为一个整数 $n~(2\leq n\leq10^5)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(0\leq a_i\leq10^9)$，第三行为 $n$ 个整数 $b_1,b_2,\cdot,b_n~(a_i\leq b_i\leq10^9)$。

输出

如果可以则输出 $YES$，否则输出 $NO$。

样例

题解

判断所有剩余可乐的体积 $\sum_{i=1}^na_i$ 能否放入体积最大的两个罐子中即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn =  100000 + 100;
int n;
LL a, sum;
LL num[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        sum = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &a);
            sum += a;
        }
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &num[i]);
        }
        sort(num, num + n);
        if(sum > num[n - 1] + num[n - 2]) {
            printf("NO\n");
        } else {
            printf("YES\n");
        }
    }
    return 0;
}

B. Wrath

题意

有 $n$ 个人站成一排，第 $i$ 个人手里有一个长度为 $L_i$ 的钩子，如果第 $j$ 个人满足条件 $j<i$ 且 $j\geq i-L_i$，那么这个人就会被杀死，铃声一响，所有人同时抛出钩子杀死前面的人，问最终有多少人存活。

输入

第一行为一个整数 $n~(1\leq n\leq10^6)$，第二行为 $n$ 个整数 $L_1,L_2,\cdots,L_n~(0\leq L_i\leq10^9)$。

输出

在铃声响后，最终有多少人存活。

样例

题解

从后往前扫描，每扫描一个人将这个人能够杀死的人的最小位置记为 $Min$，则如果这个人的位置 $i<Min$，这个人就可以存活，不论这个人是否存活，都需要将 $Min$ 更新为 $\min(Min,i-L_i)$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn =  1000000 + 100;
int n, Min, ans;
int num[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        ans = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        Min = n + 1;
        for(int i = n; i > 0; --i) {
            if(i < Min) {
                ++ans;
            }
            Min = min(Min, i - num[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Pride

题意

对于一个长度为 $n$ 的序列，可以选择其中两个相邻的数字 $x,y$，并将它们中的其中一个用 $\gcd(x,y)$ 进行替换，问至少要经过多少次操作，才能使得序列中所有数字都为 $1$。

输入

第一行为一个整数 $n~(1\leq n\leq2000)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^9)$。

输出

输出最少的操作次数，如果永远都无法达到目标，则输出 $-1$。

样例

题解

首先取一个最短的区间，这个区间的最大公约数为 $1$，通过这个长度为 $len$ 的区间得到一个 $1$ 需要的操作次数为 $len-1$，然后再利用这个 $1$ 与其他数字进行最大公约数的替换操作，操作次数等于除这个数字外，其他所有不等于 $1$ 的数字的个数，可以由此得到答案。如果整个序列的最大公约数不为 $1$，则输出 $-1$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 2000 + 100;
int n, Index, ans;
int num[maxn];
int gcd(int a, int b) {
    return (b == 0? a: gcd(b, a % b));
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        ans = n + 1;
        Index = n + 1;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 1; i <= n; ++i) {
            int Gcd = num[i];
            if(Gcd == 1) {
                Index = i;
                ans = 0;
                break;
            }
            for(int j = i + 1; j <= n; ++j) {
                Gcd = gcd(Gcd, num[j]);
                if(Gcd == 1) {
                    if(ans > j - i) {
                        ans = j - i;
                        Index = j;
                    }
                    break;
                }
            }
        }
        if(ans == n + 1) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            if(num[i] != 1 && i != Index) {
                ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Gluttony

题意

给定 $n$ 个互不相等的数字 $a_1,a_2,\cdots,a_n$，将 $n$ 个数字重新生成一个排列 $b_1,b_2,\cdots,b_n$ 后，要求对于下标的任意一个非空真子集 $\{x_1,x_2,\cdots,x_k\}(1\leq x_i\leq n,0<k<n)$，都满足条件 $\sum_{i=1}^ka_{x_i}\neq\sum_{i=1}^kb_{x_i}$。

输入

第一行为一个正整数 $n~(1\leq n\leq22)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(0\leq a_i\leq10^9)$。

输出

如果可以构造出满足条件的序列 $b$，则按顺序输出 $b$ 序列中的每一个元素，否则输出 $-1$，有多解则输出任意一个。

样例

题解

首先考虑一个更简单的问题，对于一个有序的序列 $a_1,a_2,\cdots,a_n$，如果我们将序列中的每个位置上的数字都往右移动一位，第 $n$ 个数字移动到第 $1$ 位，生成的新的序列为 $a_n,a_1,a_2\cdots,a_{n-1}$，首先考虑真子集不包含 $x_i=1$ 的情况，则可以发现对于任意一个集合，原序列中的数字都大于新序列中的数字，而如果考虑 $x_i=1$ 的情况，由于 $\sum_{i=1}^na_i$ 对两个序列都是相等的，所以包含下标为 $1$ 的情况的大小关系与不包含 $x_i=1$ 的情况正好相反，原序列中的任意一个真子集数字的和都小于新序列中的数字和，因此不论如何总是可以满足题给条件。
对于乱序的序列 $a_i$，只要用一个结构体标记一下下标即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 50;
struct Node {
    int num, Index;
};
bool operator<(const Node &a, const Node &b) {
    return a.num < b.num;
}
int n;
int num[maxn];
Node node[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            node[i].Index = i;
            node[i].num = num[i];
        }
        sort(node, node + n);
        for(int i = 1; i < n; ++i) {
            swap(node[i].Index, node[0].Index);
        }
        for(int i = 0; i < n; ++i) {
            num[node[i].Index] = node[i].num;
        }
        for(int i = 0; i < n; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", num[i]);
        }
        printf("\n");
    }
    return 0;
}