CF1443C の 解题报告
_Pecky_
2021-11-13 17:18:59
# CF1443C の 解题报告
## 一.题目背景
这道题目作为 J Y 中学的复活赛题目， 被 Pecky 在考场上想到了奇怪的性质 ~~一个小优化~~ ， Pecky 进行优化之后由于代码能力不成熟导致 $100$ 变 $30$， 所以顺手来一发这道题的题解。
------------
## 二.题目分析
有 n 道菜， 每道菜有着两个 cost ， 第一个 cost 为送餐时间， 第二个 cost 为自己取餐时间。 观察题目发现， 对 a 进行排序， 则花费的时间 $T\, = $ $max(a[i], sum_b[i + 1])$。 于是我们就想到了对 b 数组求一个后缀和， 对 $a$ 数组进行排序， 然后扫一遍取 max 即可。 复杂度为 $O(n * logn)$。
------------
## 三. Coding Time
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2 * 1e5 + 10;
struct node{
ll a;
ll b;
}l[maxn];
ll sum[maxn];
bool cmp1(node x, node y){
return x.a < y.a;
}
int main(){
int t, n;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
sum[n + 1] = 0;//初始化不要用 memset, 会 TLE
for(int i = 1;i <= n;i++){
scanf("%lld", &l[i].a);
}
for(int i = 1;i <= n;i++){
scanf("%lld", &l[i].b);
}
sort(l + 1, l + n + 1, cmp1);//对 a 进行排序
for(int i = n;i >= 1;i--){
sum[i] = sum[i + 1] + l[i].b;//求 b 的后缀和
}
ll ans = 1e9 + 10;
for(int i = 0;i <= n;i++){
ll maxx = max(l[i].a, sum[i + 1]);//计算答案
ans = min(ans, maxx);
}
printf("%lld\n", ans);
}
return 0;
}
```
------------
## 四.一个小优化（常数优化）
对于 a 数组以及 sum_b 数组， 我们排序后发现 a 数组是不严格单调递增的， 而 sum_b 数组为不严格单调递减的， 则两者取 max 会令最后的 ans 为单谷的， 所以我们可以考虑进行三分， 或者取个 mid， 分别向两边扫， 这样可以对时间复杂度进行一点点小优化。
------------
## $Code$：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2 * 1e5 + 10;
struct node{
ll a;
ll b;
}l[maxn];
ll sum[maxn];
bool cmp1(node x, node y){
return x.a < y.a;
}
int main(){
int t, n;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
sum[n + 1] = 0;
for(int i = 1;i <= n;i++){
scanf("%lld", &l[i].a);
}
for(int i = 1;i <= n;i++){
scanf("%lld", &l[i].b);
}
sort(l + 1, l + n + 1, cmp1);
for(int i = n;i >= 1;i--){
sum[i] = sum[i + 1] + l[i].b;
}
ll ans = 1e18 + 10;//注意 ans 要初始化大一些, 否则可能进不了下面的循环
//100 -> 30 の 经验教训
int mid = (n + 1) >> 1;
for(int i = mid;i >= 0;i--){
ll maxx = max(l[i].a, sum[i + 1]);
if(maxx > ans){
break;
}
ans = min(ans, maxx);
}
for(int i = mid + 1;i <= n;i++){
ll maxx = max(l[i].a, sum[i + 1]);
if(maxx > ans){
break;
}
ans = min(ans, maxx);
}
//这样最坏情况下也只会扫 n / 2次
//但是由于 sort 复杂度即为 n * logn
//所以只会优化一点点(没什么卵用)
printf("%lld\n", ans);
}
return 0;
}
``