当发现答案是单调的,从已知条件推答案不太容易,而假设知道了答案,推已知量很容易,这时可以二分
二分答案,根据判断答案不断缩小答案所在区间,最终得到答案
细节很烦。。
//lower_bound(arr, arr+n, x) == [l, r)中>=val的第一个元素位置
//upper_bound(arr, arr+n, x) == [l, r)中>val的第一个元素位置
SGU 114
题意:
思路:肯定是建在中间的某个位置最小,往左太多和往右太多肯定GG,考虑三分
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; int n; double l, r, mid1, mid2; #define eps 1e-8 struct node { int x, p; }a[16000]; bool cmp(node b, node c) { return b.x < c.x; } double cal(double y) { double ans = 0.0; for(int i = 0; i < n; i++) ans += a[i].p * 1.0 * (max(y, 1.0 * a[i].x) - min(y, 1.0 * a[i].x)); return ans; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d %d", &a[i].x, &a[i].p); sort(a, a + n, cmp); l = 1.0 * a[0].x, r = 1.0 * a[n - 1].x; while(r - l > eps) { mid1 = l + (r - l) / 3; mid2 = r - (r - l) / 3; double cmid1 = cal(mid1); double cmid2 = cal(mid2); if(cmid1 > cmid2) l = mid1; else r = mid2; } printf("%.5f ", l); return 0; }
SGU 154
题意:给一个1e8以内的数q,求最小的一个数使得它的阶乘后面有q个0,如果没有这样的数则输出-1
思路:由有多少个0推阶乘很难,但从阶乘推0的个数就容易了哇
二分时。。记录一下答案(?
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; int main() { long long q; scanf("%lld", &q); long long l = 1, r = 1e12, cnt, cntt; while(l < r) { long long mid = (l + r) / 2; cnt = 0; long long tmp = mid; while(tmp >= 5) { tmp /= 5; cnt += tmp; } if(cnt < q) l = mid + 1; else if(cnt == q) r = mid, cntt = cnt; else r = mid; } if(cntt == q) printf("%lld ", r); else printf("No solution "); return 0; }
Codeforces 278B 坑。。
在前提做了一个无用的多余的判断 wa掉了
注意0啊1啊这种特殊条件下的情况
POJ 3579
题意:给n个数,这n个数中间一共有C(n,2)个差值,求这些差值的中间值
思路:1e5的数据,因为差值最小0,最大就是最大值减最小值,考虑二分
二分中间的差值,把原数组排序后可以计算出每个a[i]有多少个数和它的差在mid以内,然后判断
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef long long LL; typedef long double LD; const int SZ = 100100; int a[SZ]; int sum, n; //lower_bound(arr, arr+n, x) == [l, r)中>=val的第一个元素位置 //upper_bound(arr, arr+n, x) == [l, r)中>val的第一个元素位置 bool check(int x) { int ans = 0; for(int i = 0; i < n; i++) ans += n-(lower_bound(a, a+n, a[i] + x) - a); if(ans > sum) return true; return false; } int main() { while(~scanf("%d", &n)) { for(int i = 0; i < n; i++) scanf("%d", &a[i]); sum = n * (n-1) / 4; sort(a, a+n); int res; int l = 0, r = a[n-1] - a[0]; while(l <= r) { int mid = (l + r) / 2; if(check(mid)) res = mid, l = mid + 1; else r = mid - 1; } printf("%d ", res); } return 0; }
Codeforces-460C
题意:n朵花有初始高度a[i],m天中每天可以给连续的w朵花浇水,问最终获得的花中最矮的花的高度最大是多少
思路:有sum数组记录到这朵花时之前的浇水有多少影响(前缀和)
sum[i+w]处数组。。sum数组要开到n+w
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define SZ 1e5+10 typedef long long LL; LL a[100010]; LL n, m, w; LL sum[200010];//每个点在当前被影响的高度 bool check(LL x)//smallest flower's height -> x { LL cnt = 0, now; memset(sum, 0, sizeof(sum)); for(int i = 0; i < n; i++) { if(i) sum[i] += sum[i-1]; now = a[i] + sum[i];//现在的高度=之前的+影响的 if(now < x) { cnt += (x - now); sum[i] += (x - now); sum[i+w] -= (x - now);//i+w之后不受这次浇水的影响 } } if(cnt <= m) return true; return false; } int main() { scanf("%lld %lld %lld", &n, &m, &w); for(int i = 0; i < n; i++) scanf("%lld", &a[i]); LL l = 1, r = 2e9, ans; while(l < r) { LL mid = (l+r+1) / 2; if(check(mid)) l = mid; else r = mid - 1; } printf("%lld ", l); return 0; }