Codeforces Round #448 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #448 (Div. 2)
过题数：2
排名：729/8334

A. Pizza Separation

题意

将一个披萨分成 $n$ 块小扇形，每块小扇形的圆心角为 $a_i$，现在要求从这些小扇形中选出一部分连续的小扇形，要求这些连续的小扇形组成的大扇形与剩下的所有小扇形组成大扇形的圆心角和的差的绝对值最小，求最小的圆心角度差的绝对值。

输入

第一行为一个整数 $n~(1\leq n\leq360)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq360)$，且数据保证 $\sum_{i=1}^n=360$。

输出

输出答案。

样例

输入	输出	提示
4 90 90 90 90	0	第一部分可以选择第 $1$ 和第 $2$ 块扇形，另一部分可以选择第 $3$ 和第 $4$ 块扇形， 这样结果就是 $|(90+90)-(90+90)|=0$。
3 100 100 160	40
1 360	360	由于只有一块扇形，所以只能将这块扇形分到其中一部分，另一部分无法分到扇 形，所以结果为 $|360-0|=360$。
4 170 30 150 10	0	第一部分可以选择第 $1$ 和第 $4$ 块扇形，所以结果就是 $|(170+10)-(30+150)|=0$。扇形的分配如图：

题解

暴力 $n^2$ 便利所有的区间取最小值。

过题代码

#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 = 400;
int n;
int num[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 = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        int ans = 1000;
        for(int i = 1; i <= n; ++i) {
            int tmp = 0;
            for(int j = i; j <= n; ++j) {
                tmp += num[j];
                ans = min(ans, abs(tmp - (360 - tmp)));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. XK Segments

题意

在一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 中，找到所有的有序对 $(i,j)$，要求 $(i,j)$ 满足 $a_i\leq a_j$，在区间 $[a_i,a_j]$ 内恰好有 $k$ 个整数能整除 $x$，问有多少个有序对满足条件。

输入

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

输出

输出满足条件的有序对的个数。

样例

题解

先将整个数组排序，枚举起点 $i$，二分查找第一个大于等于 $\lceil\frac{num_i}{x}\rceil\times x+(k-1)x$ 的整数位置 $itl$，以及第一个大于等于 $\lceil\frac{num_i}{x}\rceil\times x+kx$ 的整数的位置 $itr$，则所有以 $i$ 为起点的满足条件的有序对的个数为 $itr-itl$。最后注意特判 $k=0$ 的情况。

过题代码

#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 x, k, ans;
LL num[maxn];
LL *itl, *itr;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%I64d%I64d", &n, &x, &k) != EOF) {
        ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &num[i]);
        }
        sort(num, num + n);
        for(int i = 0; i < n; ++i) {
            LL l = (num[i] + x - 1) / x * x + (k - 1) * x;
            LL r = (num[i] + x - 1) / x * x + k * x;
            if(k == 0) {
                l = num[i];
                r = (num[i] + x - 1) / x * x;
            }
            itl = lower_bound(num, num + n, l);
            itr = lower_bound(num, num + n, r);
            ans += itr - itl;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}