Salary Changing
Thinking
这道题第一思路就是二分，模拟了一下样例，感觉好像行于是就开始写。
对于二分，我们一定是二分中位数是什么，二分的边界对我们来说是非常重要的，所以我们在二分前有必要确认我们的二分边界，因为一定有
∑
i
=
1
n
l
i
<
=
s
\sum _{i = 1} ^ {n} l_i <= s
∑i=1nli<=s，所以我们对
l
l
l数组
s
o
r
t
sort
sort一遍，得到
l
e
f
t
=
l
m
i
d
left = l_{mid}
left=lmid，同样的，对
r
r
r数组
s
o
r
t
sort
sort一遍，得到
r
i
g
h
t
=
r
m
i
d
right = r_{mid}
right=rmid，接下来我们就可以开始我们的二分了。
但是这道题的难点不是在二分思想上，而是
j
u
d
g
e
judge
judge函数有点难写：
首先我们对每一个人的
s
a
l
a
r
y
salary
salary按照
r
r
r从小到大排序。接下来，我们可以通过二分得到
s
a
l
a
r
y
l
<
=
m
i
d
<
=
s
a
l
a
r
y
r
salary_l <= mid <= salary_r
salaryl<=mid<=salaryr的人数量
n
u
m
num
num，如果
n
<
n
/
2
+
1
n < n / 2 + 1
n<n/2+1这个二分值过大，直接返回false。否则我们进行贪心的选值，记录下这些点的
s
a
l
a
r
y
l
salary_l
salaryl，然后进行排序，优先选择小的去补充我们所需的
s
a
l
a
r
y
<
m
i
d
salary < mid
salary<mid，但是还没有选满的。接下来就是对于
s
a
l
a
r
y
>
=
m
i
d
salary >= mid
salary>=mid的进行贪心选，假设他的
s
a
l
a
r
y
l
>
x
salary_l > x
salaryl>x就选择
s
a
l
a
r
y
l
salary_l
salaryl，否则的话就是选择
x
x
x。
下面代码中有更详细的描述
j
u
d
g
e
judge
judge函数。
Coding
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef pair
<int, int> pii
;
const double pi
= acos(-1.0);
const double eps
= 1e-7;
const int inf
= 0x3f3f3f3f;
inline ll
read() {
ll f
= 1, x
= 0;
char c
= getchar();
while(c
< '0' || c
> '9') {
if(c
== '-') f
= -1;
c
= getchar();
}
while(c
>= '0' && c
<= '9') {
x
= (x
<< 1) + (x
<< 3) + (c
^ 48);
c
= getchar();
}
return f
* x
;
}
const int N
= 2e5 + 10;
ll L
[N
], R
[N
], n
, s
, m
;
struct Node
{
int l
, r
;
bool operator < (const Node
& t
) const {
return r
< t
.r
;
}
}a
[N
];
bool judge(int x
) {
int p
= lower_bound(R
+ 1, R
+ 1 + n
, x
) - R
;
int last
= n
- p
+ 1;
if(last
< m
) return false;
vector
<int> v
;
for(int i
= p
; i
<= n
; i
++) v
.pb(a
[i
].l
);
sort(v
.begin(), v
.end());
int need
= m
- 1 - (p
- 1);
ll sum
= L
[p
- 1];
for(int i
= 0; i
< need
; i
++) {
sum
+= v
[i
];
if(v
[i
] > x
) return false;
}
for(int i
= need
; i
< v
.size(); i
++) sum
+= max(x
, v
[i
]);
return sum
<= s
;
}
int main() {
int _
= read();
while(_
--) {
n
= read(), s
= read();
m
= n
/ 2 + 1;
for(int i
= 1; i
<= n
; i
++) {
a
[i
].l
= read(), a
[i
].r
= read();
L
[i
] = a
[i
].l
, R
[i
] = a
[i
].r
;
}
sort(a
+ 1, a
+ 1 + n
);
sort(L
+ 1, L
+ 1 + n
);
sort(R
+ 1, R
+ 1 + n
);
int l
= L
[(n
>> 1) + 1], r
= R
[(n
>> 1) + 1];
for(int i
= 1; i
<= n
; i
++)
L
[i
] = a
[i
].l
+ L
[i
- 1];
while(l
< r
) {
int mid
= l
+ r
+ 1 >> 1;
if(judge(mid
)) l
= mid
;
else r
= mid
- 1;
}
printf("%d\n", l
);
}
return 0;
}
