糖果传递
题目要求
题目描述：
有 n 个小朋友坐成一圈，每人有 a [ i ] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1 。
求使所有人获得均等糖果的最小代价。
输入格式：
第一行输入一个正整数 n ，表示小朋友的个数。
接下来 n 行，每行一个整数 a [ i ] ，表示第 i个小朋友初始得到的糖果的颗数。
输出格式：
输出一个整数，表示最小代价。
数据范围：
1≤n≤1000000,
0≤a[i]≤2×109,
数据保证一定有解。
输入样例：
4
1
2
5
4
输出样例：
4
思路分析
那么根据题意有递归式：
a1−x1+x2=avg
a2−x2+x3=avg
...
an−1−xn−1+xn=avg
an−xn+x1=avg
上式变形：
x1−x2=a1−avg
x2−x3=a2−avg
...
xn−1−xn=an−1−avg
xn−x1=an−avg
继续变形：
xn=x1+an−avg
xn−1=x1+an+an−1−2∗avg
...
x2=x1+an+an−1+...+a2−(n−1)∗avg
x1=x1+0
化简：
令cn=−(an−avg)
令cn−1=−(an+an−1−2∗avg),则有：
xn=x1−cn
xn−1=x1−cn−1
...
x2=x1−c2
x1=x1−c1,c1=0
则本题又变成了求：min(∣x1−c1∣+∣x1−c2∣+...+∣x1−cn∣)
其中i=ci+1−ai+avg,c1=0
就变得和上题一样了，我们只需要处理好 c 之后按照上题所述即可。
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 1000010; int a[N]; int c[N]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); LL sum = 0; for (int i = 1; i <= n; i ++ ) sum += a[i]; int avg = sum / n; c[1] = 0; for (int i = n; i > 1; i -- ) c[i] = c[i + 1] - a[i] + avg; sort(c + 1, c + n + 1); LL res = 0; for (int i = 1; i <= n; i ++ ) res += abs(c[i] - c[(i + 1) / 2]); printf("%lld\n", res); return 0; }
雷达设备
题目要求
题目描述：
假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
每个小岛都位于海洋一侧的某个点上。
雷达装置均位于海岸线上，且雷达的监测范围为 d ，当小岛与某雷达的距离不超过 d 时，该小岛可以被雷达覆盖。
我们使用笛卡尔坐标系，定义海岸线为 x 轴，海的一侧在 x 轴上方，陆地一侧在 x 轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。
输入格式：
第一行输入两个整数 n 和 d，分别代表小岛数目和雷达检测范围。
接下来 n 行，每行输入两个整数，分别代表小岛的 x ，y 轴坐标。
同一行数据之间用空格隔开。
输出格式：
输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 − 1 。
数据范围：
1≤n≤1000,
−1000≤x,y≤1000
输入样例：
3 2
1 2
-3 1
2 1
输出样例：
2
思路分析
这个题可以转换成一个区间问题，我们如果去枚举雷达然后判断是否有小岛在雷达范围内是十分复杂的，所以我们可以反过来去思考：我们根据每一个小岛的位置去计算雷达可以处在的位置，根据勾股定理可以知道，每个小岛所对应的雷达可放置的区域是一个区间，那么我们要让雷达数目最小，就是对这些区间进行处理，先对区间按照右端点进行排序，对于每一个区间，我们都选择其右端点的位置作为雷达的放置点，这样就可以让每个雷达保证跨越更大的范围。
代码
#include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 1010; struct Segment { double l, r; bool operator < (const Segment t) const { return r < t.r; } }seg[N]; int main() { int n, d; cin >> n >> d; bool flag = false; for (int i = 0; i < n; i ++ ) { int x, y; scanf("%d%d", &x, &y); if (d < y) flag = true; else { double len = sqrt(d * d - y * y); seg[i] = {x - len, x + len}; } } if (flag) puts("-1"); else { sort(seg, seg + n); double st = -1e9; int cnt = 0; for (int i = 0; i < n; i ++ ) if (seg[i].l > st) { cnt ++; st = seg[i].r; } printf("%d\n", cnt); } return 0; }
