测试点没有c=0的情况,严格来讲用stl的bound函数应该有个特判
  • 板块P1102 A-B 数对
  • 楼主A_pier
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/11/4 11:31
  • 上次更新2023/11/4 01:28:28
查看原帖
测试点没有c=0的情况,严格来讲用stl的bound函数应该有个特判
571939
A_pier楼主2021/11/4 11:31

下面这是看出测试点中没有c=0情况的代码

#include<iostream>
#include<algorithm>
using namespace std;

long long a[200001];

int main()
{
	int n, c;
	cin >> n >> c;
   //有下面这两行代码也可以ac,这就说明测试点中 
   //没有c=0的情况,不严谨,而且,我看了前两页的
   //题解发现用这种方法的都写错了:要么没特判, 
   //要么特判错误,第二段代码将会给出我的特判
	if(c==0)
	   cout<<-1<<endl;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	long long ans = 0;
	for (int i = 0; i < n; i++) 
		ans += ((upper_bound(a, a + n, a[i] + c) - a) - (lower_bound(a, a + n, a[i] + c) - a));
	cout << ans << endl;

	return 0;
}

可能有疏漏,写的有点糙,但是懒得再改了,╰( ̄ω ̄o)大神要是发现毛病,还请及时告知,谢谢

#include<iostream>
#include<algorithm>
using namespace std;

long long a[200001];

int main()
{
	int n, c;
	cin >> n >> c;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		if (c != 0)
			ans += ((upper_bound(a, a + n, a[i] + c) - a) - (lower_bound(a, a + n, a[i] + c) - a));
		else {
			int k = ((upper_bound(a, a + n, a[i] + c) - a) - (lower_bound(a, a + n, a[i] + c) - a));//重复数字个数
			ans += 2*((k*(k - 1)) / 2);
			i += k;//注意这里i要加k
			//最外层括号内表示组合数公式C[n,2],再乘2是因为1-1=0与1-1=0是两个不同的数对(题目要求),虽然大小相同
			//赠送测试c=0情况数据 n=3 c=0 a[i]=1 ,1 ,1 答案=6
		}
	}
	cout << ans << endl;

	return 0;
}
2021/11/4 11:31
加载中...