cf Educational Codeforces Round 115 (Rated for Div. 2) C题

类型：二分查找。

中文题目：

C.删除两项内容

Monocarp有一个由n个整数组成的数组a。让我们将k表示为这些元素的数学平均值（注意，k可能不是整数）。

n个元素数组的数学平均值是元素之和除以这些元素的数量（i。 e、和除以n）。

Monocarp希望从a中删除两个元素，以便剩余元素（n）的数学平均值−2）元素仍然等于k。

您的任务是计算位置对[i，j]（i<j）的数量，这样，如果删除这些位置上的元素，则（n）的数学平均值−2）剩余元素等于k（即，它等于原始数组a的n个元素的数学平均值）。

简化：给一串数，去掉其中两个数，使去掉后的串的平均值等于原平均值，问有几种方案。

如：

输入：

5

1 4 7 3 5

输出：

2

代码：

#include<bits/stdc++.h>

using namespace std;

#define cout(x) printf("%d",x)

#define cin(x) scanf("%d",&x)

#define ll long long

int a[200010];

int main(){

	ll sum,t,n;

	cin>>t;

	int ans;

	while(t--){

		memset(a,0,sizeof(a));

		ll num=0;

		ll sum=0;

		cin>>n;

		for(int i=0;i<n;i++){

			cin>>a[i];

			sum+=a[i];

		}

		double ans=sum*1.0/n;

		ans*=2;

		sort(a,a+n);

		for(int i=0;i<n;i++){

			num+=upper_bound(a,a+n,ans-a[i])-lower_bound(a,a+n,ans-a[i]);

			if(ans-a[i]==a[i])num--;

		}

		cout<<num/2<<endl;

	}

	return 0;

}

巴特西

CF回顾《二分类》

cf Educational Codeforces Round 115 (Rated for Div. 2) C题

类型：二分查找。

中文题目：

简化：给一串数，去掉其中两个数，使去掉后的串的平均值等于原平均值，问有几种方案。

如：

思路：

开始想直接暴力查找，果然TLE。后来没想到怎么优化。其实想到二分但太复杂，不想写。重点没学会map和查找函数.

最重点：

函数upper_bound（a,a+n,x）-a 查找出最晚出现的X的下标

lower_bound(a,a+n,x)-a 查找出第一个出现的x的下标

都在algorithm里

最新文章

热门文章