文章目录
- 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=)