题目：
ZJM 有 n 个作业，每个作业都有自己的 DDL，如果 ZJM 没有在 DDL 前做完这个作业，那么老师会扣掉这个作业的全部平时分。所以 ZJM 想知道如何安排做作业的顺序，才能尽可能少扣一点分。请你帮帮他吧！
Input:
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4
Output:
0
3
5
标题既然是二分，这题就应该……好吧这题其实是上一次题目的延申。这是一道贪心题。思想也很简单。首先根据ddl，从大到小排列，因为比如第四天，第一天ddl 的事情你根本……毫无能力做什么。
所以就倒着来，没到一天，就把这一天ddl的所有事情扔进一个大根堆里面，每天从堆顶取一个元素就是今天要干的事情
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct ddl1
{
int ddl;
int score;
bool operator<(const ddl1 a) const
{
return score < a.score;
}
};
ddl1 a[2000];
bool cmp(ddl1 &x, ddl1 &y)
{
if (x.ddl > y.ddl)
{
return 1;
}
else if (x.ddl < y.ddl)
{
return 0;
}
else
{
return x.score > y.score;
}
}
int main()
{
int m;
cin>>m;
int max;
while(m)
{
max=0;
int sum = 0;
int kam = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i].ddl;
if(a[i].ddl>max)
{
max=a[i].ddl;
}
}
for (int i = 0; i < n; i++)
{
cin >> a[i].score;
sum += a[i].score;
}
sort(a, a + n, cmp);
priority_queue<ddl1> pq;
int x = 0;// 往后走的进度
for (int i = max; i > 0; i--)
{
for (int j = x; j < n; j++)
{
if (a[j].ddl == i)
{
// cout << "hello" << endl;
pq.push(a[j]);
x++;
}
if (a[j].ddl != i)
break;
}
if (!pq.empty())
{
ddl1 ks = pq.top();
kam += ks.score;
// cout << " " << ks.score << endl;
pq.pop();
}
}
int tmp = sum - kam;
//cout << sum << endl;
// cout << kam << endl;
cout << tmp << endl;
m--;
}
return 0;
}
不太难，有了基本思路就开始码了。
2.ZJM 有四个数列 A,B,C,D，每个数列都有 n 个数字。ZJM 从每个数列中各取出一个数，他想知道有多少种方案使得 4 个数的和为 0。
当一个数列中有多个相同的数字的时候，把它们当做不同的数对待。请你帮帮他吧！
in
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
out
5
这题是一个典型的简单的二分。既然是要找四个组里面的元素，首先想到的是O（n4）的遍历，但你也看见可怕的时间复杂度，所以不妨先把两组里面的和都给找出来，看看是不是能匹配相反数。这样时间复杂度就暴降了，然后用个快排再用个二分查找时间复杂度就是O（n2 lognlogn）
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a, int b)
{
return a < b;
}
int tmp = 0;
void findit(int a[], int lf, int rt, int k)
{
while (lf <= rt)
{
int w = (lf + rt) / 2;
if (k == a[w])
{
lf = w + 1;
}
else if (k < a[w])
{
rt = w - 1;
}
else if (k > a[w])
{
lf = w + 1;
}
}
for(int d=lf;d>0;d--)
{
if(a[d]==k)
{
tmp++;
}
else
{
break;
}
}
}
int a[4000 + 5];
int b[4000 + 5];
int a2[4000 + 5];
int b2[4000 + 5];
int c[16000000 + 5];
int main()
{
int n;
cin >> n;
int tl = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i] >> b[i] >> a2[i] >> b2[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
c[tl] = a[i] + b[j];
tl++;
}
}
c[tl]=1000000000;
tl++;
sort(c, c + tl, cmp);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
findit(c, 0, tl-1 , -(a2[i] + b2[j]));
/* if ()
{
tmp++;
}*/
}
}
findit(c, 0, tl-1 , 17);
cout << tmp << endl;
return 0;
}
题目：
TT 是一位重度爱猫人士，每日沉溺于 B 站上的猫咪频道。有一天，TT 的好友 ZJM 决定交给 TT 一个难题，如果 TT 能够解决这个难题，ZJM 就会买一只可爱猫咪送给 TT。任务内容是：给定一个 N 个数的数组 cat[i]，并用这个数组生成一个新数组 ans[i]。新数组定义为对于任意的 i, j 且 i != j，均有 ans[] = abs(cat[i] - cat[j])，1 <= i < j <= N。试求出这个新数组的中位数，中位数即为排序之后 (len+1)/2 位置对应的数字，’/’ 为下取整。TT 非常想得到那只可爱的猫咪，你能帮帮他吗？
Input：
4
1 3 2 4
3
1 10 2
Output：
1
8
这几乎是全部题目中第一个难题（很难理解）
首先二分的条件
1.有序列
2.能计算中位数是不是要找的数
3.能计算中位数是比要找的数大还是小
然后该题重点是，计算名次。
首先max=最大数减去最小数。min=0。
计算名次的方法：如果将X从小到大排列可以去绝对值。那么计算𝑋𝑗−𝑋𝑖≤𝑃的二元组对数即可。移项可得𝑋𝑗≤𝑋𝑖+𝑃, 𝑖<𝑗。
有了这个方法。我们针对最大值与最小值中间 的数就可以计算出来一个名词。
然后条件2.3就满足了。因为中位数的名次其实我们也是知道的（（n-1）n/2+1）/2
然后一也是可以知道的，这种情况下就实现了二分的所有条件！
#include<iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1000000];
/*
*/
int paiming(int x, int n)
{
int sum = 0;
/*for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[j] <= a[i] + x)
{
sum++;
}
else break;
}
}*/
for (int i = 0; i < n; i++)
{
sum += n - (lower_bound(a, a + n, a[i] + x) - a);
}
//cout << " " << sum << endl;
return sum;
}
int main()
{
int n;
while (cin >> n)
{
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
//cin>>a[i];
}
sort(a, a + n);
int rt = a[n - 1] - a[0];
int weizhi = ((n - 1)*n / 2 + 1) / 2;
int lf = 0;
while (lf < rt)
{
int w = (lf + rt) / 2;
int dl = paiming(w, n);
if (dl > (n*(n - 1) / 2 - weizhi))
{
//cout << "1" << endl;
//rt = w;
lf = w + 1;
}
else//if (dl <= weizhi)
{
//cout << "2" << endl;
//lf = w + 1;
rt = w;
}
}
cout << (lf-1) << endl;
}
return 0;
}
计算名次的过程我开始是直接统计的，可惜暴了一点错误（其实根本原因是遍历的时候下标没控制好）。不过我没改，直接换了C++自带的lower_bound（）返回的是数值 第一个 出现的位置。（其实就是偷懒了QAQ）
