二分好题
A. 1.喂养宠物 - 「基础算法」第3章 二分算法强化训练 - 高效进阶 - 课程 - YbtOJ
这是一道简单题。就是我们枚举一下我们选择的\(m\)个兔子，然后求出所有兔子的价值，之后我们排序，从小到大选择。
code:
#include <bits/stdc++.h>
//#define int long long
using namespace std;
inline int read() {
int x = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return w * x;
}
int n, m;
struct node {
int v, w;
} a[55];
/*bool cmp(node a,node b){
if(a.w<b.w)return true;
else if(a.w==b.w)return a.v<b.v;
else return false;
}*/
int p[1000];
void pd(int x) {
memset(p, 0, sizeof(p));
for (int i = 1; i <= n; i++) p[i] = a[i].v + a[i].w * (x - 1);
sort(p + 1, p + n + 1);
}
bool check(int mid) {
int tot = 0;
pd(mid);
for (int i = 1; i <= mid; i++) {
tot += p[i];
if (tot > m)
return false;
}
// cout<<"!!!!!!!!!!!!!!!!!!!!!!!!"<<tot<<endl;
return tot <= m;
}
int ans;
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i].v = read();
for (int i = 1; i <= n; i++) a[i].w = read();
// sort(a+1,a+n+1,cmp);
int l = 0, r = n;
// for(int i=1;i<=n;i++)
// cout<<a[i].v<<" "<<a[i].w<<endl;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
l = mid + 1, ans = mid;
} else
r = mid - 1;
}
cout << ans << endl;
return 0;
}
B. 2.最小时间 - 「基础算法」第3章 二分算法强化训练 - 高效进阶 - 课程 - YbtOJ
这道题是A题的一道升级题，同样的思路，只是在上题\(sort\)的时候改为nth-element，就可以A掉这道题，注意题目是不超过\(m\)个物品，所以我们要在每次加的时候都要判断，要不这样我们会WA，只有76分。
nth-element讲解
nth-element的时间复杂度是O(n)，所以要比sort快，但在数据小的时候最坏时间复杂度是O(n^2),因为函数原理是随机访问，但实际运用过程中，基本都会是O(n)的时间复杂度。所以说是非常迅速的。
接下来展示一下nth-element的操作:
将第k_th元素放到它该放的位置上，左边元素都小于等于它，右边元素都大于等于它.
有一个序列a，有n个元素，查找第m大个元素，nth-element一般是升序
nth-element(a+1,a+m+1,a+n+1);
但这个不会给你的前面的东西排序
我们可以用一个比较函数来完成
bool operator<(const node &G) const { return val > G.val; }（这是从大到小的）
bool operator<(const node &G) const { return val < G.val; }（这是从小到大的）
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return w * x;
}
struct node {
int k, b;
int val;
bool operator<(const node &G) const { return val > G.val; }
} a[1000005];
int n, m, s;
int ans;
bool check(int x) {
for (int i = 0; i < n; i++) a[i].val = a[i].k * x + a[i].b;
int res = 0;
nth_element(a, a + m, a + n);
for (int i = 0; i < m; i++) {
if (a[i].val > 0)
res += a[i].val;
if(res>=s) return true;
}
return false;
}
signed main() {
n = read(), m = read(), s = read();
for (int i = 0; i < n; i++) a[i].k = read(), a[i].b = read();
int l = 0, r = 1000000008;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid))
ans = mid,r = mid - 1;
else
l = mid + 1;
}
cout << ans << endl;
return 0;
}
C. 3.攻击法坛 - 「基础算法」第3章 二分算法强化训练 - 高效进阶 - 课程 - YbtOJ
这是一道\(DP+二分\) ,有一说一，我不会，但在我不断学习下，渐渐的懂了。
我们设一个\(L1[i]\) 表示在 \(i\) 这个位置使用长度为 \(j\) 的魔法，\(L2[i]\)表示在 \(i\) 这个位置使用长度为 \(j*2\) 的魔法。\(f[i][j]\)是在使用了\(i\)次第一根法杖，\(j\)次第二根法杖后哪能覆盖到的最远的法坛的序号。
转移方程：
for(int i=0;i<=t1;i++)
for(int j=0;j<=t2;i++){
if(i!=0) f[i][j] = L1[f[i - 1][j] + 1];
if(j!=0) f[i][j] = max(f[i][j], L2[f[i][j - 1] + 1])
}
这样我们就能完美的解决这道题
像这种求最小值（最优）的，一定要想到区间DP，这是一种悟性~~，在做题的过程中增长。
code:
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 2500;
int f[N][N];
int L1[N], L2[N];
inline int read() {
int x = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return w * x;
}
int n, t1, t2;
int a[N];
int ans;
bool check(int mid) {
memset(L1, 0, sizeof(L1));
memset(L2, 0, sizeof(L2));
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
if (a[j] <= a[i] + mid - 1)
L1[i] = j;
if (a[j] <= a[i] + mid * 2 - 1)
L2[i] = j;
}
L1[n + 1] = n;//L1的n+1一定要赋值为n,要不然会在后面的转移方程中会把f[i][j]变成0
L2[n + 1] = n;//L1的n+1一定要赋值为n,要不然会在后面的转移方程中会把f[i][j]变成0
for (int i = 0; i <= t1; i++)
for (int j = 0; j <= t2; j++) {
if (i != 0)
f[i][j] = L1[f[i - 1][j] + 1];//在这里会变成0
if (j != 0)
f[i][j] = max(f[i][j], L2[f[i][j - 1] + 1]);
}
return f[t1][t2] == n;
}
int main() {
n = read(), t1 = read(), t2 = read();
for (int i = 1; i <= n; i++) a[i] = read();
if (t1 + t2 >= n) {//如果我们加起来都大于n了，那我们直接输出1就可以了。
printf("1");
return 0;
}
sort(a + 1, a + n + 1);
int l = 0, r = 1e9;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid))
r = mid - 1, ans = mid;
else
l = mid + 1;
}
cout << ans << endl;
return 0;
}
D. X.分割矩阵 - 「基础算法」第3章 二分算法强化训练 - 高效进阶 - 课程 - YbtOJ
好，这是一道好题。
数组划分的二维拓展，我们可以先扫行，再扫列。这道题还要用到贪心的思想。
二维的题一定要从行列中分别考虑，但也有的题要转换建图，这是我们在这里不讨论的。
我们知道如果我们选择了第i行开始割，那我们就绝对不会选择i+1行，因为这样一定不优，接着我们用一个sum数组来存储
该行的价值，如果他的价值到达了我们可以割的界限，那我们就把它给割掉，但我们在中间会出现其中一个很大的现象，那
我们就要仔细处理一下，这时候我们可以再考虑我们的列，如果我们这列大于mid，我们就割，这就是贪心。最后我们查询
是不是割的行数是A，割的列数是B。
code:
#include <bits/stdc++.h>
//#define int long long
using namespace std;
inline int read() {
int x = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return w * x;
}
int n, m, A, B;
int a[505][505], sum[505][505];
bool f(int L, int r, int x) {
int cnt = 0, s = 0;
for (int j = 1; j <= m; j++) {
s += sum[r][j] - sum[L - 1][j];
if (s >= x) {//大于就割
cnt++;
s = 0;
}
}
if (cnt < B)
return false;
return true;
}
bool check(int mid) {
int cnt = 0, L = 1;
for (int i = 1; i <= n; i++) {
if (f(L, i, mid)) {//可割
cnt++;
L = i + 1;
}
}
if (cnt < A)
return false;
return true;
}
int ans;
int main() {
n = read(), m = read(), A = read(), B = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
a[i][j] = read();
sum[i][j] = sum[i - 1][j] + a[i][j];
}
int l = 0, r;
for (int j = 1; j <= m; j++) r += sum[n][j];
while (l <= r) {
int mid = l + r >> 1;
if (check(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
cout << ans << endl;
return 0;
}
将停一段时间，因为我的图论太差了/kk
标签：二分,ch,int,mid,read,while,getchar From： https://www.cnblogs.com/qlwybz/p/18007515