Codeforces-Round#561 Div.2

目录

• A题
  • 基本思路：
• C题
  • 基本思路：

A题

基本思路：

假设n个学生开始字母相同，则分成n/2和n-n/2两对的配对数最少

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;cin>>n;int a[26]={0};
	for(int i=0;i<n;i++)
	{
		string s;cin>>s;
		a[s[0]-'a']++;
	}
	int sum=0;
	for(int i=0;i<26;i++)
	{
		int s1=a[i]/2,s2=a[i]-s1;
		sum+=s1*(s1-1)/2+s2*(s2-1)/2;
	}
	cout<<sum<<endl;
	return 0;
}

C题

基本思路：

取绝对值排序，然后取i~i*2的配对数，用二分查找(注意数据大小范围)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[200010];
int cmp(int a,int b)
{
	return a<b;
}
int main()
{
	ll n;cin>>n;
	for(ll i=0;i<n;i++)
	{
		cin>>arr[i];
		if(arr[i]<0)arr[i]*=-1;
	}
	sort(arr,arr+n,cmp);
	ll cnt=0;
	for(ll i=0;i<n-1;i++)
	{
		ll num=upper_bound(arr,arr+n,arr[i]*2)-arr;
		cnt+=num-i-1;
	}
	cout<<cnt<<endl;
	return 0;
}