題目：
ZJM 有 n 個作業(yè)，每個作業(yè)都有自己的 DDL，如果 ZJM 沒有在 DDL 前做完這個作業(yè)，那么老師會扣掉這個作業(yè)的全部平時分。所以 ZJM 想知道如何安排做作業(yè)的順序，才能盡可能少扣一點分。請你幫幫他吧！
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
標(biāo)題既然是二分，這題就應(yīng)該……好吧這題其實是上一次題目的延申。這是一道貪心題。思想也很簡單。首先根據(jù)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 有四個數(shù)列 A,B,C,D，每個數(shù)列都有 n 個數(shù)字。ZJM 從每個數(shù)列中各取出一個數(shù)，他想知道有多少種方案使得 4 個數(shù)的和為 0。
當(dāng)一個數(shù)列中有多個相同的數(shù)字的時候，把它們當(dāng)做不同的數(shù)對待。請你幫幫他吧！
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）的遍歷，但你也看見可怕的時間復(fù)雜度，所以不妨先把兩組里面的和都給找出來，看看是不是能匹配相反數(shù)。這樣時間復(fù)雜度就暴降了，然后用個快排再用個二分查找時間復(fù)雜度就是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。任務(wù)內(nèi)容是：給定一個 N 個數(shù)的數(shù)組 cat[i]，并用這個數(shù)組生成一個新數(shù)組 ans[i]。新數(shù)組定義為對于任意的 i, j 且 i != j，均有 ans[] = abs(cat[i] - cat[j])，1 <= i < j <= N。試求出這個新數(shù)組的中位數(shù)，中位數(shù)即為排序之后 (len+1)/2 位置對應(yīng)的數(shù)字，’/’ 為下取整。TT 非常想得到那只可愛的貓咪，你能幫幫他嗎？
Input：
4
1 3 2 4
3
1 10 2
Output：
1
8
這幾乎是全部題目中第一個難題（很難理解）
首先二分的條件
1.有序列
2.能計算中位數(shù)是不是要找的數(shù)
3.能計算中位數(shù)是比要找的數(shù)大還是小
然后該題重點是，計算名次。
首先max=最大數(shù)減去最小數(shù)。min=0。
計算名次的方法：如果將X從小到大排列可以去絕對值。那么計算?????????≤??的二元組對數(shù)即可。移項可得????≤????+??, ??<??。
有了這個方法。我們針對最大值與最小值中間 的數(shù)就可以計算出來一個名詞。
然后條件2.3就滿足了。因為中位數(shù)的名次其實我們也是知道的（（n-1）n/2+1）/2
然后一也是可以知道的，這種情況下就實現(xiàn)了二分的所有條件！
#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;
}
計算名次的過程我開始是直接統(tǒng)計的，可惜暴了一點錯誤（其實根本原因是遍歷的時候下標(biāo)沒控制好）。不過我沒改，直接換了C++自帶的lower_bound（）返回的是數(shù)值 第一個 出現(xiàn)的位置。（其實就是偷懶了QAQ）
