前言
看了看舍友写的，很优雅，发现有些时候虽然可以交的上去，但是不同思路的代码长度差距非常之大。
另外第一题想遍历数组的，应该写成a[j]写成了j，调试了半天才看出来。第二题被调函数传错数了，连WA11次，陷入了深深自我怀疑，有点小小难受。
第一题
题目： Light It Up
题意：
在x-y的坐标轴上有n个人分别坐在不同的点上，其中有k个人坐的地方有一盏灯，每盏灯可以照亮半径为r的圆。要求我们求出所有人都被照亮时，如果所有灯的半径相同，那么最小可以是多少。
输入格式
第一行是两个整数n和k。
第二行是k个整数，表示所在位置有灯的人的序号。
第三行到n+2行，每行只有两个整数（xi，yi）表示序号为i的人所在的位置。
输出格式
输出一个实数，表示灯的最小半径。要求结果误差小于-105。
数据范围
1 ≤ K < N ≤ 1000
1 ≤ A1 < A2 < ⋯ < AK ≤ N
∣Xi∣, ∣Yi∣ ≤ 105
保证每个点只会有一个人。
输入样例：
4 2
2 3
0 0
0 1
1 2
2 0输出样例：
2.23606797749978969思路：
- 贪心。题目要求我们找到当所有人都被覆盖时，灯的最小半径。
- 首先我们必须满足每个人都被至少一个灯的半径覆盖，那么可以先遍历所有人，然后对每个人遍历所有灯，对每个人维护人和其它灯距离的最小值。最后再排一次序，输出所有人的距离最大值就好了。
- 为什么是最大值？因为要满足所有人都被照到，我们维护的距离是当前这个人距离其它灯的最小值，那么所能接受距离的最低限度就是所有最小距离中的最大值。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3 + 10;
#define long long LL;
int a[N];
pair<int, int>p[N];
double b[N];
double slove(int i, int j)
{
int x = abs(p[j].first - p[i].first);
int y = abs(p[j].second - p[i].second);
return (double)sqrt((double)x*x+(double)y*y);
}
int main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= k; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i)cin >> p[i].first >> p[i].second;
//遍历每个人，找到每个人被照到的最小范围，然后在所有范围中找到最大的
for (int i = 1; i <= n; ++i)
{
b[i] = 1e9;
for (int j = 1; j <= k; ++j)
b[i] = min(b[i], slove(i,a[j]));
}
sort(b + 1, b + n + 1);
printf("%.12lf\n", b[n]);
return 0;
}第二题
题目： ±1 Operation
题意：
给我们四个数X，A，D，N，其中A，D，N组成一个首项为A，公差为D，共有N项的等差数列。每次可以将X的值加一或者减一，求解最少几次可以将X变为该等差数列中的一项。
输入格式
输入只有四个整数：X，A，D，N
输出格式
一个整数，表示对X的操作次数。
数据范围
−1018 ≤ X, A ≤ 1018
−106 ≤ D ≤ 106
1 ≤ N ≤ 1012
输入样例：
-555555555555555555 -1000000000000000000 1000000 1000000000000输出样例：
444445思路：
- 我们可以设B为该等差数列的尾项，如果X小于首项或者大于尾项，那么操作次数分别是X和首项或尾项差的绝对值。
- 如果X的值在该数列首尾两项之间，由于数据范围极大，暴力循环是一定会超时的，所以考虑二分。
- 需要注意的是在进行二分时，需要考虑D的符号问题，要将A和B的值互换，同时不要忘记将D的值取反。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3 + 10;
#define LL long long
//给我们一个数字x，让我们用最少的操作次数将x变为一个好数字
//好数字定义：有一个n项的数列s，s1=a，公差为d
void slove(LL x, LL a, LL d, LL n, LL b)
{
if (x <= a)
cout << a - x;
else if (x >= b)
cout << x - b;
else
{
LL l = 0, r = n - 1;
while (l < r)//找到第一个大于等于x的数。
{
LL mid = (l + r) / 2;
if ((mid * d + a) >= x) r = mid;
else l = mid + 1;
}
LL k1 = (l * d + a)-x;
LL k2 = x - ((l - 1) * d + a);
cout << min(k1,k2);
}
}
int main()
{
LL x, a, d, n;
cin >> x >> a >> d >> n;
LL b = a + d * (n - 1);
if (d >= 0) slove(x, a, d, n, b);
else slove(x, b, -d, n, a);
return 0;
}
