文章目錄
- A-DDL的恐懼
-
- 題意
- 思路
- 代碼
- B-四個數列
-
- 題意
- 思路
- 代碼
- C-TT的神秘禮物
-
- 題意
- 思路
- 代碼
A-DDL的恐懼
題意
ZJM 有 n 個作業，每個作業都有自己的 DDL，如果 ZJM 沒有在 DDL 前做完這個作業，那麼老師會扣掉這個作業的全部平時分。
是以 ZJM 想知道如何安排做作業的順序，才能盡可能少扣一點分。
Input
輸入包含T個測試用例。輸入的第一行是單個整數T，為測試用例的數量。
每個測試用例以一個正整數N開頭(1<=N<=1000)，表示作業的數量。
然後兩行。第一行包含N個整數，表示DDL，下一行包含N個整數，表示扣的分。
Output
對于每個測試用例，您應該輸出最小的總降低分數，每個測試用例一行。
思路
貪心就完了
先按照扣的分數從大到小排個序（扣分較多的比較重要）
盡量把所有作業安排到ddl當天做，那天實在沒辦法做就向前尋找空閑的時間做。這裡可以開n個桶來代表有n天，我們向前尋找的時候隻要看這個桶是否被一個作業占用，否就占用，是就往前找，直到第0個桶，也就是這個作業做不了了，此時答案 ans 加上這題所扣的分
代碼
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
#define RF(i,a,n) for(register int i=a;i>=n;i--)
#define inf 1e9
#pragma GCC optimize(2)
using namespace std;
const int maxn = 100005;
struct node{
int t, p;
bool operator < (const node &b) const{
return p>b.p;
}
}a[maxn];
int b[maxn];
int T, n;
int main(){
ios::sync_with_stdio(false);
cin>>T;
while(T--){
memset(b,0,sizeof(b));
int ans = 0;
cin>>n;
For(i,1,n) cin>>a[i].t;
For(i,1,n) cin>>a[i].p;
sort(a+1,a+1+n);
For(i,1,n){
int t = a[i].t;
while(t && b[t]) {t--;}
if(t==0) ans+=a[i].p;
b[t] = 1;
}
cout<<ans<<endl;
}
return 0;
}
————————————————————————————————————————————
B-四個數列
題意
ZJM 有四個數列 A,B,C,D，每個數列都有 n 個數字。ZJM 從每個數列中各取出一個數，他想知道有多少種方案使得 4 個數的和為 0。
當一個數列中有多個相同的數字的時候，把它們當做不同的數對待。
Input
第一行：n（代表數列中數字的個數） （1≤n≤4000）
接下來的 n 行中，第 i 行有四個數字，分别表示數列 A,B,C,D 中的第 i 個數字（數字不超過 2 的 28 次方）
Output
輸出不同組合的個數。
思路
這題資料比較大，直接周遊想必是不行的，對于這類查找的問題，周遊不行那就二分吧
因為是找a+b+c+d四個數的和為0的組合數，并不用寫出具體的數字，所有我們可以合并一下a和b，c和d。
那麼現在問題就變成了簡單的 A + B = 0 (A=a+b, B=c+d)的問題，移項得到 B = -A。
最終我們隻需要周遊A中的所有元素，去B中二分地尋找-A。
代碼
#include<iostream>
#include<algorithm>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
using namespace std;
const int maxn = 20000005;
int n, ans;
int a[10][maxn];
int main(){
ios::sync_with_stdio(false);
cin>>n;
For(i,1,n){
For(j,1,4){
cin>>a[j][i];
}
}
int tot = 0;
For(i,1,n){
For(j,1,n){
a[5][++tot] = a[1][i]+a[2][j];
a[6][tot] = a[3][i]+a[4][j];
}
}
sort(a[6]+1,a[6]+tot+1);
For(i,1,tot){
int pos1 = lower_bound(a[6]+1,a[6]+tot+1,-a[5][i])-a[6];
int pos2 = upper_bound(a[6]+1,a[6]+tot+1,-a[5][i])-a[6];
if(pos1 != pos2)
ans += pos2-pos1;
}
cout<<ans<<endl;
return 0;
}
————————————————————————————————————————————
C-TT的神秘禮物
題意
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 位置對應的數字，’/’ 為下取整。
Input
多組輸入，每次輸入一個 N，表示有 N 個數，之後輸入一個長度為 N 的序列 cat， cat[i] <= 1e9 , 3 <= n <= 1e5
Output
輸出新數組 ans 的中位數
思路
這題如果枚舉，C(n,2)且n<=1e5，肯定TLE。然而這題是求中位數，是以又可以二分了
題目要求的是 a[j] - a[i] <= d =====> a[j] <= a[i] + d
這就很神奇了，我們本來要求的是一個新的數組的中位數，現在可以在原數組中解決了。
我們二分d，統計小于a[j]的個數。
🌰🌰：
設數組a = {1,2,3,4}
∴ abs(aj-ai) = {1,1,1,2,2,3}
中位數位置 pos = C(n,2)/2 = 3
最終 ans = 1
設 d = 2
i=1(索引從1開始) 1，2，3，4 a[j]=a[i]+d=3 小于a[j]的：2，3 cnt = 2
i=2 2, 3, 4 a[j]=a[i]+d=4 小于a[j]的：3，4 cnt = 2
i=3 3, 4 a[j]=a[i]+d=5 小于a[j]的：4 cnt = 1
i=4 4 a[j]=a[i]+d=5 小于a[j]的：沒有 cnt = 0
cnt = 2+2+1+0 = 5 > pos = 3 不滿足(不是我們要找的中位數)
縮小範圍……
PS：這題cout白給。
代碼
#include<iostream>
#include<cstring>
#include<algorithm>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
using namespace std;
const int maxn = 100005;
int n, tot;
int a[maxn];
int jg(int d)
{
int cnt = 0;
For(i,1,n){
cnt += upper_bound(a+i+1,a+n+1,a[i]+d)-(a+i+1);
}
return cnt>=tot;
}
int main(){
while(~scanf("%d",&n)){
For(i,1,n){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
tot = n*(n-1)/2;
tot = (tot+1)/2;
int l = 0, r = a[n]-a[1]+1;
while(r-l>1){
int mid = (l+r)>>1;
if(jg(mid))
r = mid;
else
l = mid;
}
printf("%d\n",r);
}
return 0;
}
![二分法查找二分法查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)