P9421 [蓝桥杯 2023 国 B] 班级活动 - 洛谷
建立序号数组，记录每个序号的个数，从小打大排序
如果出现次数为1，a++；
如果出现次数为2，跳过
如果出现次数大于2
这个数-1然后a-1，逻辑是：拿大于2的元素，去帮助等于1的元素凑成2
如果a已经为0 ，那么这个数-1，a+1,逻辑是：大于2的数，拿出一个数补充a
来看代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int>arr(n+1);
for (int i = 0; i < n; i++)
{
int now;
cin >> now;
arr[now]++;
}
sort(arr.begin(), arr.end());
int a = 0;
int b = 0;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
//等于 0 的跳过
if (arr[i] == 1)
{
a++;
}
//等于2的跳过
//大于2的
if (arr[i] > 2)
{
while (arr[i] > 2)
{
if (a == 0)
{
arr[i]--;
a++;
}
else
{
arr[i]--;
a--;
}
cnt++;
}
}
}
cnt += a / 2;
cout << cnt << "\n";
}
P9422 [蓝桥杯 2023 国 B] 合并数列 - 洛谷
说说我的思路吧:
既然是把一个数分成两个数组数，那么最差情况定义了：从头加到尾才相等，
我一直在想有没有最优算法，难想是真的，但是有没有呢，
听我说说，我们定义两个int型 a和b，a做arr的指针 b做brr的指针
当arr[a]>brr[b],brr需要合并，小于时，a需要合并
等于时a++，b++，
来看代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int>arr(n);
vector<int>brr(m);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < m; i++)
{
cin >> brr[i];
}
//骗分：
int a = 0, b = 0;
int cnt = 0;
while (1)
{
if (arr[a] > brr[b])
{
brr[b + 1] += brr[b];
b++;
cnt++;
}
else if (arr[a] == brr[b])
{
a++;
b++;
}
else
{
arr[a + 1] += arr[a];
a++;
cnt++;
}
if (a == n - 1 && b == m - 1)
{
break;
}
}
cout << cnt << "\n";
}
我们遍历每个点，它们都当一次顶点，计算顶点与其余所有点的距离，根据距离公式：
但是考虑到小数点，无理数，我们选择不开根号
对于距离相同的点，考虑组合算法，C（n，2），n个点随机取2个点，成一个组合。
如果不足2就不算。
但是还要考虑三点共线，对于所有的离顶点距离相同的点，我们可以视为他们在以顶点为圆心，距离为半径的圆上，三点共线，那么他们圆上两点的距离一定是直径，是圆上两点之间最长距离，具有唯一性。
首先将所有的点记录在map中，当我们计算出其中一点对于顶点的距离后，用性质算出三点共线对应点的坐标，使其作为键，查询map中的值，如果存在，三点共线情况++；
值得注意的是三点共线情况的两点会互相重复计算，最后减的时候记得/2。
来看代码：
#include<bits/stdc++.h>
using namespace std;
long long combination_n_choose_2(long long n) {
if (n < 2) return 0; // n < 2 时组合数无效
// 先除2再乘，避免整数溢出风险
if (n % 2 == 0) {
return (n / 2) * (n - 1);
}
else {
return n * ((n - 1) / 2);
}
}
int main()
{
int n;
cin >> n;
vector<pair<int, int>>points(n);
map<pair<int, int>,int>counter;
for (int i = 0; i < n; i++)
{
cin >> points[i].first >> points[i].second;
counter[points[i]] = 1;
}
int sum = 0;
//枚举点：
for (int i = 0; i < n; i++)
{
int cnt = 0;
int recnt = 0;
pair<int, int> dingdian = points[i];
map<long long, long long>dis;
for (int j = 0; j < n; j++)
{
if (j == i)
{
continue;
}
long long x = dingdian.first - points[j].first;
long long y = dingdian.second - points[j].second;
long long len = x * x + y * y;
dis[len]++;
//计算对手：
pair<int, int>annim;
annim.first = 2 * dingdian.first - points[j].first;
annim.second = 2 * dingdian.second - points[j].second;
auto it = counter.find(annim);
if (it != counter.end())
{
recnt++;
}
}
for (auto& it : dis)
{
sum += combination_n_choose_2(it.second);
}
sum -= recnt/2;
}
cout << sum << endl;
}
