A - DDL 的恐惧
现有n个作业，每个作业都有DDL，没在DDL之前做完作业的话，就没扣掉相应的分。
输入
第一行输入指的是准备要输入程序的有几组数据，接下来每组数组有两行，第一行是每个作业的DDL，第二行是每个作业的分值
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
输出
0
3
5
思路
考虑贪心算法。
每个作业都有分值，所以当然要考虑把分值大的先拿下。所以把数据给存进结构体了以后，就先按找分值降序，日期降序保存，这样就保证先插分值高的数据，分值相同的数据就先插日期比较靠后的，这样就会对其他数据的插入产生最小的影响。
总结
对一道题考虑贪心算法的时候至少要自己先简单证明一下正不正确，如果有些摸棱两可的地方不妨多想想，或许有更好的贪心算法。
代码
#include<iostream>
#include<algorithm>
using namespace std;
struct day {
int a, b;//a记录的是ddl，b记录的是扣分
bool operator<(const day& p) const {
//第一关键字降序，第二关键字降序
if (b != p.b) return b > p.b;
return a > p.a;
}
}days[9999];
bool vis[9999];//用来插这次访问过的
void cal(int k)//用来计算要扣掉多少分
{
int sum=0;
int j;
for (int i = 0; i < k; i++)
{
for (j = days[i].a; j >= 1; j--)
{
if (!vis[j])
{
vis[j] = true;
break;
}
}
if (j == 0)
sum += days[i].b;
}
cout << sum<<endl;
for (int i = 0; i < 3000; i++)
vis[i] = false;
}
int main()
{
int n;
cin >> n;//输入一共有多少组数据
for (int i = 0; i < n; i++)
{
int k;
cin >> k;//输入这组数据中一共有多少个ddl
for (int j = 0; j < k; j++)
{
cin >> days[j].a;
}
for (int j = 0; j < k; j++)
{
cin >> days[j].b;
}
sort(days, days + k);
cal(k);
}
}
B - 四个数列
现有4个数列，现要从4个数列中挑出4个数字其和为0，考虑其组合的个数。
输入
一行是一组数据
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
输出
5
思路
一开始我使用的map，之前在leetcode上做过相似的题，只是那道题是用unordered_map做的，这次不支持C++11，就只能用map，复杂度高了一点，做出来的复杂度是O(n^2logn)，和上课学的方法复杂度一样，但是可能常数比较大，所以没过。
map方法代码
#include<iostream>
#include<map>
using namespace std;
int A[4000];//四个数组
int B[4000];
int E[4000];
int F[4000];
int main()
{
int n;
cin >> n;
int k = 0;
bool pan = true;
map<int, int> C;
for (int i = 0; i < n; i++)
{
scanf("%d %d %d %d",&A[i],&B[i],&E[i],&F[i]);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[A[i] + B[j]]++;
}
}
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j =0; j < n; j++)
{
//if (C.count(-(E[i] + F[j])) != 0)
sum+=C[-(E[i] + F[j])];
}
}
cout << sum;
这样的话只能乖乖用课上的方法，一看四个数组，第一个想到的可能是一个四重循环枚举所有的数得到结果，但是复杂度是O（）根本不能接受好吗。
所以可以先每两个数组作为一个单位，枚举其中的每两个数的和，这样的话4个数组就变成了两个数组A和B，复杂度降到了O（）,这可以接受了，在得到B后，要是把B给升序排列，然后从B中找A中对应的数的时候，还能二分查找，那么复杂度还能降低，是O（
）更优！
总结
这道题考虑降低复杂度以及二分查找的使用，启示是只要有序的排列都能二分降低复杂度
AC代码
#include<stdio.h>
#include<algorithm>
using namespace std;
int A[5000];
int B[5000];
int C[5000];
int D[5000];
int E[9999999];
int F[9999999];
int cal(int n,int k)
{
int sum=0,ans=-1;
n=-n;
int l=0,r=k-1;
int mid=(l+r)>>1;
while(l<=r)
{
mid=(l+r)>>1;
if(F[mid]>=n){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(F[ans]!=n)
return 0;
else
{
for(int i=ans;i<k;i++)
{
if(F[i]==n)
sum++;
else
break;
}
}
return sum;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
int k=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
E[k]=A[i]+B[j];
k++;
}
}
k=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
F[k]=C[i]+D[j];
k++;
}
}
sort(F,F+k);
int sum=0;
int bb;
for(int i=0;i<k;i++)
sum+=cal(E[i],k);
printf("%d",sum);
}
C - TT 的神秘礼物
现在给出一个数组，然后让数组中每两个序号不同的数相减取绝对值生成一个新数组，求这个新数组的中位数
输入
每两行为一组数据，第一行代表这个数组有多少个数，第二行输入这个数组
4
1 3 2 4
3
1 10 2
输出
1
8
思路
求中位数要排序，排序之后就会有序，有序就能用二分。
如果顺着题目中的思路，那就是先给数组求中位数然后排序再找中位数，但是这样的结果是复杂度O（）不能接受。
那就改良，使用二分。
首先要去掉绝对值，那么就给目标数组排序，这样从大到小相减的时候就不用求绝对值了。然后开始对所有有可能的答案进行二分搜索，已知的答案的最大值是目标数组的最后一个数减去第0个数，但是最小的未知，但一定大于等于0，那就设置最小值是0，这样的话对这里面的数进行二分，每次二分的结果都去数组里面找他所在的名次，如果名次是中位数的名次了，那么中位数就在它的附近。
那么名次怎么找呢，那就要枚举，先有一个二分出来的数x，让数组里面每个数与其后的所有数相减，这时候用二分枚举，得到最后一个差值<=x的数的位置，每个数组里的数都这么做一遍，就能得到这个数x的名次。
一直按上面的步骤计算x的名次，直到枚举x的左右游标相等时，即x是目标中位数。
总结
这道题考察二分搜索，是二分答案的典型题，使用二分搜索能有效降低代码的复杂度。
代码
#include<iostream>
#include<algorithm>
using namespace std;
int cat[999999];
int n;
int search(int mid)
{
int r, l;
int midd;
int sum = 0;
int ans = 0;
for (int i = 0; i < n - 1; i++)
{
ans = 0;
r = n - 1;
l = i;
while (r >= l)
{
midd = (r + l) >> 1;
if (cat[midd] - cat[i] <= mid)
{
ans = midd;
l = midd + 1;
}
else
r = midd - 1;
}
sum += (ans - i);
}
return sum;
}
int main()
{
while (cin >> n)
{
for (int i = 0; i < n; i++)
scanf_s("%d", &cat[i]);
sort(cat, cat + n);
long long r = cat[n - 1] - cat[0];
long long l = 0;
long long mid;
int result = n * (n - 1) >> 1;
if (result % 2 == 1)//他是奇数
result = (result >> 1) + 1;
else
result = result >> 1;
long long th;
long long now;
while (r >= l)
{
mid = (r + l) >> 1;
th = search(mid);
if (th >= result)
{
now = mid;
r = mid - 1;
}
else
l = mid + 1;
}
printf("%d\n", now);
}
}
