当发现答案是单调的，从已知条件推答案不太容易，而假设知道了答案，推已知量很容易，这时可以二分
二分答案，根据判断答案不断缩小答案所在区间，最终得到答案
细节很烦。。
//lower_bound(arr, arr+n, x) == [l, r)中>=val的第一个元素位置
//upper_bound(arr, arr+n, x) == [l, r)中>val的第一个元素位置
SGU 114
题意：
思路：肯定是建在中间的某个位置最小，往左太多和往右太多肯定GG，考虑三分
#include#include #include #include #include using namespace std;int n;double l, r, mid1, mid2;#define eps 1e-8struct 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\n", l); return 0;}
SGU 154
题意：给一个1e8以内的数q，求最小的一个数使得它的阶乘后面有q个0，如果没有这样的数则输出-1
思路：由有多少个0推阶乘很难，但从阶乘推0的个数就容易了哇
二分时。。记录一下答案（？
#include#include #include #include #include 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\n", r); else printf("No solution\n"); return 0;}
Codeforces 278B 坑。。
在前提做了一个无用的多余的判断 wa掉了
注意0啊1啊这种特殊条件下的情况
POJ 3579
题意：给n个数，这n个数中间一共有C(n,2)个差值，求这些差值的中间值
思路：1e5的数据，因为差值最小0，最大就是最大值减最小值，考虑二分
二分中间的差值，把原数组排序后可以计算出每个a[i]有多少个数和它的差在mid以内，然后判断
#include#include #include #include #include #include #include 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\n", res); } return 0;}
Codeforces-460C
题意：n朵花有初始高度a[i]，m天中每天可以给连续的w朵花浇水，问最终获得的花中最矮的花的高度最大是多少
思路：有sum数组记录到这朵花时之前的浇水有多少影响（前缀和）
sum[i+w]处数组。。sum数组要开到n+w
#include#include #include #include using namespace std;#define SZ 1e5+10typedef 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\n", l); return 0;}