牛牛看云（二分 or 枚举）

题面链接

https://ac.nowcoder.com/acm/contest/23106/H

题面

思路 思路一

对于 ∑ i = 1 n ∑ j = i n ∣ a i + a j − 1000 ∣ \sum_{i=1}^n\sum_{j=i}^n |a_i+a_j-1000| ∑i=1n​∑j=in​∣ai​+aj​−1000∣这个等式我们会发现， a i a_i ai​的顺序不会对答案造成影响，那么我们很容易想到二分来做，我们先对其排序，然后对每一个i的位置对 1000 − a i 1000-a_i 1000−ai​进行二分操作，左半边是负数，右半边是正数，我们统计一下贡献值就好啦

思路二

因为 a i a_i ai​的数据范围很小只有[0,1000]，我们很显然也能想到用桶排的思想记录每个数出现的次数，然后直接枚举 i , j i,j i,j对即可，这也是出题人的初衷

代码 二分代码

#include
using namespace std;
//----------------�Զ��岿��----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------�Զ��岿��----------------
ll n,m,q,a[N],pre[N];


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	cin>>n;
	for(int i = 1;i >a[i];
	}
	sort(a+1,a+1+n);
	for(int i = 1;i