思路：正难则反

首先，$[1,s]$区间，最多只有$s-1$对数满足条件，例如$(1,s-1),(2,s-2),...$

然后我们可以将禁止使用的数存到一个集合中，然后遍历这个集合，如果在集合中，找到一对数满足$a+b=s$，则答案-2

特殊的，当$a=b$时，答案只需要-1即可

时间复杂度

$O(n)$

c++代码

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int>vec(n, 0);
	unordered_set<int>s;
	for (int i = 0; i < n; i++)
		cin >> vec[i];
	sort(vec.begin(), vec.end());
	int sum;
	cin >> sum;
	int count = 0;
	for (int i = 0; i < n; i++) {
		if (vec[i] >= sum)
			continue;
		if (vec[i] > sum / 2)
		{
			if (s.find(sum - vec[i]) == s.end())
				s.insert(sum - vec[i]);
		}
		else
		{
			if (s.find(vec[i]) == s.end())
				s.insert(vec[i]);
		}
	}
	// 一共种数
	int tot = sum - 1;
	if (sum % 2 == 0)
	{
		if (s.count(sum / 2))
			cout << tot - 1 - 2 * (s.size() - 1) << endl;
		else
			cout << tot - 2 * (s.size()) << endl;
	}
	else
		cout << tot - 2 * (s.size()) << endl;
	return 0;
}

python代码

n = int(input())
v = list(map(int, input().split()))
st = set()

for i in range(n):
    st.add(v[i])

s = int(input())
ans = s - 1

for g in v:
    if g < s and g in st:
        if g * 2 == s:
            ans -= 1
        else:
            ans -= 2
    st.discard(g)
    st.discard(s - g)

print(ans)

Java代码

import java.util.*;

class Main {
    public static void main(String[]args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A  = new int[n];
        Set<Integer> vst = new HashSet();
        for (int i = 0 ; i < n ; i++) {
            A[i] = sc.nextInt();
            vst.add(A[i]);
        }
        int s = sc.nextInt();

        long res = 0;
        
        for (int a: A) {
            if (vst.contains(a)) {
                if (a < s) {
                    if (a >> 1 == s) res -= 1;
                    else res -= 2;
                }
                
            }
            vst.remove(a);
            vst.remove(s-a);
        }

        System.out.println(res + s - 1);

    }
}

题目描述

小红在玩一个数学游戏，他出一个正整数$s$，你需要找出两个正整数$x$，$y$相加等于这个数，即$x+y==s$。但是他觉得这样他简单了，所以他限制了一些数不能使用，即$x$，$y$都不能使用禁止的数。现在问你有多少种$x$，$y$满足这个条件。

输入描述

第一行输入一个正整数n，表示限制的个数。

第二行输入n个正整数$a_i$，表示限制该数的使用。

第三行输入一个正整数s。

$1≤n≤200000,1≤aᵢ,s≤10⁹$,保证每个禁着点都是不相等的。

输出描述

多少种满足条件的x，y。

示例1

输入

4
1 2 3 5
10

输出

2

说明 可以选择的方案有: <4,6>,<6,4>这两种。