一.STL的二分函数
1.binary_search(ar, ar + n, x);
三个参数，第一个是数组首地址，第二个是数组名+数组大小，第三个数要找的数。
存在这个数则返回true，否则返回false；
2.lower_bound(ar, ar + n, x);
参数和上面那个一样，返回的是第一个大于或等于x的数的迭代器，减去数组首地址得到的是这个数的下标
3.upper_bound(ar, ar + n, x);
参数一样，这个返回的是第一个大于x的位置。
POJ2785 4 Values whose Sum is 0
题意：
有4组数，让你从每组中找一个数，然后这4个数和为0，有几种找法。
分析：
暴力枚举肯定超时，我们可以将两组何为一组，这样即可将四组变为两组，然后对于第一组的每一个数x，在第二组中二分查找-x出现的次数
AC代码：
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
int n;
int a[4050], b[4050], c[4050], d[4050];
vector<int> vt;
ll ans;
int x;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
vt.push_back(a[i] + b[j]);
}
}
sort(vt.begin(), vt.end());
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
x = -(c[i] + d[j]);
ans += upper_bound(vt.begin(), vt.end(), x) - lower_bound(vt.begin(), vt.end(), x);
}
}
printf("%lld\n", ans);
return 0;
}
二.二分答案 + 检验
通常用于解决答案有单调性的问题，就大于某个数符合题意，小于某个数就不符合这种题目。
对于像求那种最大的最小值，最小的最大值的题目，常用三种（两种）方法：1.贪心 2.二分 3.动态规划
牛棚 poj - 2456 （模板题）
题意：
分析：
AC代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int n, c;
int ar[100050];
int mid, l, r;
int ans;
bool judge(int x)
{
int cnt = 1, previous = ar[1];
for(int i = 2; i <= n; ++i)
{
if(ar[i] - previous >= x)
{
previous = ar[i];
cnt++;
}
if(cnt >= c) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &c);
for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
sort(ar + 1, ar + n + 1);
l = 1;
r = ar[n];
while(l <= r)
{
mid = (l + r) >> 1;
if(judge(mid))
{
l = mid + 1;
ans = max(ans, mid);
//cout << ans << endl;
}
else r = mid - 1;
}
printf("%d\n", ans);
return 0;
}晒衣服 poj - 3404
题干 略
注意两点：
1.使用佩奇的话，是在佩奇和自然风的共同作用下干了k个单位的水，佩奇实际上干了k - 1个单位的水。
2.根据上面一点，k - 1有可能是个0，除以0会re。
AC代码：
//#include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k;
int ar[100050];
int l, r, mid;
int ans = 1000000000;
int mx;
bool judge(int x)
{
int sum = 0;
int temp;
for(int i = 1; i <= n; ++i)
{
if(ar[i] > x)
{
temp = ((ar[i] - x) + (k - 2)) / (k - 1);
sum += temp;
}
if(sum > x) return false;
}
return true;
}
int main()
{
scanf("%d", &n);
for(int i = 1;i <= n; ++i)
{
scanf("%d", &ar[i]);
mx = max(mx, ar[i]);
}
scanf("%d", &k);
if(k == 1)
{
printf("%d\n", mx);
return 0;
}
l = 1;
r = mx;
while(l <= r)
{
mid = (l + r) >> 1;
if(judge(mid))
{
r = mid - 1;
ans = min(ans, mid);
}
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
NC19916 [CQOI2010]扑克牌
分析：
首先，很明显这个题可以二分，那就需要考虑判断函数的写法，对于一个x，要组成x副牌，我们可以求出需要多少张joker，判断这个数字与m的大小，除此之外，最多只能用x张joker，否则会出现一副牌里有多个joker的现象，所以还要比较这个数与x的大小。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int n, m;
int ar[55];
int mx;
int l, r, mid;
bool judge(int x)
{
int sum = 0;
for(int i = 1; i <= n; ++i)
{
if(x > ar[i])
{
sum += x - ar[i];
}
if(sum > m || sum > x) return false;
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &ar[i]);
mx = max(mx, ar[i]);
}
l = 0;
r = mx + m;
while(l <= r)
{
mid = (l + r) >> 1;
if(judge(mid)) l = mid + 1;
else r = mid - 1;
}
printf("%d\n", l - 1);
return 0;
}
NC16564 借教室
分析：
如果第n单无法满足，那势必造成某一天教室数量小于0且，这天的教室数量永远不会大于0了。对于单个订单是从某一天到某一天教室数减少，这个用到差分，这点我这没想到，并且理解了好长时间。
对于一开始的数组，我们差分处理它。然后二分答案，检验x的过程如下：
首先复制一遍差分数组，得到数组temp[]，将前x单执行，即利用差分的性质，
将temp[s[i]] -= d[i]; temp[t[i] + 1] += d[i];
然后对这个数组求前缀和，即将差分数组还原回原数组，对于原数组每一个元素，判断它是否为负数，只要有一个为负数，就说明前x单无法完成。
另外，要注意这个找到的第一个不符合标准的。注意一下判断函数return的true和false；
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int ar[1000050], temp[1000050];
int d[1000050], s[1000050], t[1000050];
int l, r, mid, ans;
bool judge(int x)
{
for(int i = 1; i <= n; ++i) temp[i] = ar[i];
for(int i = 1; i <= x; ++i)
{
temp[s[i]] -= d[i];
temp[t[i] + 1] += d[i];
}
ll sum = 0;
for(int i = 1; i <= n; ++i)
{
sum += temp[i];
if(sum < 0) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
for(int i = n; i > 0; --i) ar[i] -= ar[i - 1];
for(int i = 1; i <= m; ++i) scanf("%d%d%d", &d[i], &s[i], &t[i]);
l = 1;
r = m;
while(l < r)
{
mid = (l + r) >> 1;
if(judge(mid)) r = mid;
else l = mid + 1;
}
if(judge(r)) printf("-1\n%d\n", r);
else printf("0\n");
return 0;
}
NC14301K-th Number
题意：
对数列A的每个区间求第K大，并将第k大插入到B中，再求B的第M大。
分析：
二分 + 尺取
二分x，尺取区间，记录区间中大于等于x的数字个数num，如果num == k，那么固定左指针，右指针向后移动的功程中会有n - j + 1个区间，这些区间中第k大的数一定大于或等于x，之后，左指针右移，判断移除区间的那个数于x的关系，进而改变num，累加这样的区间数得到sum，这个sum便是x在数组b中排第几，将这个数与m作比较返回true or false。
AC代码：
#include <bits/stdc++.h>n
using namespace std;
typedef long long ll;
ll t, n, k, m;
ll ar[100050];
ll l, r, mid, ans;
bool judge(ll x)
{
ll sum = 0, num = 0;
for(int i = 1, j = 1; j <= n; ++j)
{
if(ar[j] >= x) num++;
if(num == k)
{
sum += n - j + 1;
while(ar[i] < x)
{
sum += n - j + 1;
++i;
}
num--;
++i;
}
}
return sum >= m;
}
int main()
{
scanf("%lld", &t);
while(t--)
{
scanf("%lld%lld%lld", &n, &k, &m);
for(int i = 1; i <= n; ++i) scanf("%lld", &ar[i]);
l = 1;
r = 1e9;
ans = 0;
while(l <= r)
{
mid = (l + r) >> 1;
if(judge(mid))
{
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
printf("%lld\n", ans);
}
return 0;
}
01分数规划
有一堆物品，每个物品有一个价值v和代价c，从中取k个物品，是的所取物品的价值之和除以代价之和最大，求这个商。
分析：
设这个商为x，变式得到Σ（v - c * x） = 0，我们求出所有物品的v - c * x，并以此为标准排序，取前k个物品，求这k个物品的价值和除以代价和，如果这个数大于x，说明x并不是最大，如果小于x，说明根本就到不了x，即x大了。
模板题NC14662 小咪买东西
AC代码：
#include <bits/stdc++.h>
using namespace std;
int t, n, k;
int l, r, mid;
struct node
{
int c, v;
int y;
} ar[10050];
bool cmp(struct node a, struct node b)
{
return a.y > b.y;
}
bool judge(int x)
{
for(int i = 1; i <= n; ++i) ar[i].y = ar[i].v - x * ar[i].c;
sort(ar + 1, ar + n + 1, cmp);
int vv = 0, cc = 0;
for(int i = 1; i <= k; ++i)
{
vv += ar[i].v;
cc += ar[i].c;
}
if(vv / cc >= x) return true;
else return false;
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
l = 999999999;
r = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d%d", &ar[i].c, &ar[i].v);
l = min(l, ar[i].v/ar[i].c);
r = max(r, ar[i].v/ar[i].c);
}
while(l <= r)
{
mid = (l + r) >> 1;
if(judge(mid)) l = mid + 1;
else r = mid - 1;
}
printf("%d\n", l - 1);
}
return 0;
}
京公网安备 11010502036488号