• 牛客算法課 (算法入門班) 二分, 三分, 01分數規劃

    NC19916[CQOI2010] 撲克牌

    我們二分答案, 有多少套牌.

    然後如果二分出來的是 x套牌, 我們檢查, 組成x套牌需要用到多少張joker, 如果joker的數量超過x, 說明同一個組合裡用到了超過1張的joker. 我們還要檢查使用的joker 有沒有超過題目限定的m.

    NC116564 [NOIP2012]借教室

    給定每天有多少個教室可以借. 和. 每天有多少份訂單(包括借出和反還時間 和 數量).

    暴力思路, 直接遍歷每天的訂單 同時 修改每天可以借出的教室, 用 O(n * m * (t - s)),這個顯然會超時.

    由於我們知道, 如果某一個天所有教室都借出去了, 然後有人再借那麼他就會是負數, 然後他後面所有的天數都是不滿足條件的.

    我們考慮二分最後一個可行的天數.

    利用差分數組對 區間內的數字進行修改, 看看有沒有負數, 如果有負數, 表示 答案在前面, 如果沒有負數 表示答案在後面.

    為了防止出錯, 我們把借出時間 做一個排序.

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. int n, m;
    4. struct node{
    5.     int l, r, d;
    6. }a[10000000];
    7. long long r[1000000];
    8. long long del[1000000];
    9. bool check(int x){
    10.     for(int i = 1; i <= n; i++){
    11.         del[i] = r[i] - r[i - 1];
    12.     }
    13.     for(int i = 1; i <= x; i++){
    14.         del[a[i].l] -= a[i].d;
    15.         del[a[i].r + 1] += a[i].d;
    16.     }
    17.     long long sum = 0;
    18.     for(int i = 1; i <= n; i++){
    19.         sum += del[i];
    20.         if(sum < 0)return false;
    21.     }
    22.     return true;
    23. }
    24. int main(){
    25.     cin >> n >> m;
    26.     for(int i = 1; i <= n; i++){
    27.         cin >> r[i];
    28.     }
    29.     for(int i = 1; i <= m; i++){
    30.         cin >> a[i].d >> a[i].l >> a[i].r;
    31.     }
    32.     int l = 0, r = m;
    33.     while(l <= r){
    34.         int mid = (l + r) / 2; 
    35.         if(check(mid))l = mid + 1;
    36.         else r = mid - 1;
    37.     }
    38.     if(l > m)cout << 0 << endl;
    39.     else cout << -1 << endl << l << endl;
    40.     return 0;
    41. }

     這裡要注意一個點. 就是我們的差分數組 每次都重新計算, 因為我們現在是要計算到底 x 是不是一個合法日期, 而不是整個所有日子是不是都是合法日期. 

    K-th Number

    最簡單的想法是直接枚舉第m大的可能.

    因為我們知道第m大 x 意味著 他必須有m - 1 個數比x要大. 那麼我們直接去找所有區間看看 我們枚舉的x 是不是有m - 1個第k大比他大.

    那麼我們知道其實這是一個單調性問題. 所以我們選擇二分這個x的可能性. 

    那麼我們怎麼去統計有多少個區間的第k大比x 要大呢?

    我們對給定的數組進行排序, 然後一旦我們在某一區間[l , r]中發現剛剛好裡面有k個數字比x大, 那麼我們就知道 第k大的數不可能是x, 而且他會比x大. 就可以直接統計區間的數量 用n - r + 1.

    這裡就是普通的尺取法了.

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int N=1e5+500;
    4. typedef long long ll;
    5. ll n,k,m;
    6. int w[N],b[N];
    7.  
    8. bool check(int u)//双指针检测就好了. 
    9. {
    10.     int l=1,r=0;//维护它为第k大的区间.
    11.     int num=0;//维护这个区间里有多少小于等于u的数. 
    12.     ll res=0;
    13.     while(l<=n){
    14.         //統計比u大的數有多少個
    15.         while(r<=n&&num<k){
    16.             if(w[++r]>=u)num++;    
    17.         }
    18.         //一旦有k個 立馬結算
    19.         if(num==k)res+=n-r+1;
    20.         //尋找下一個區間
    21.         if(w[l]>=u){
    22.             num--;
    23.         }
    24.         l++;
    25.     }
    26.     return res>=m;
    27. }
    28.  
    29. int main()
    30. {
    31.     std::ios::sync_with_stdio(false);
    32.     std::cin.tie(0);
    33.     int T;
    34.     cin >> T;
    35.     while(T--)
    36.     {
    37.         cin >> n >> k >> m;
    38.         for(int i=1;i<=n;i++){
    39.             cin >> w[i];
    40.             b[i]=w[i];
    41.         }
    42.         //去掉連續出現的相同數字.
    43.         int r=unique(b+1,b+1+n)-b-1;
    44.         int l=1;
    45.         sort(b+1,b+1+r);
    46.         int ans=0;
    47.         while(l<=r)
    48.         {
    49.             int mid=(l+r)>>1;
    50.             if(check(b[mid]))//当我二分的这个值数量大于等于m时,要放大. 
    51.             {
    52.                 l=mid+1;
    53.                 ans=max(ans,b[mid]);
    54.             }
    55.             else r=mid-1;//否则要缩小 
    56.         }
    57.         printf("%d\n",ans);
    58.     }return 0;
    59. }

    三分思路

    如果有一個函數 存在峰值, 我們先求 l 到 mid 的mid 我們姑且叫他做lmid, 同理求出rmid, 然後如果lmid 比 rmid大證明, 峰值不可能存在於rmid 到r的區間, 我們捨去他. 如此類推 直到求出峰值.

    如何求出lmid? 

    我先把l 到 r 等分分割三段. 让l + 上这个长度, 就算到lmid 了, rmid 就是让r - 上这个长度.

    三分的模板

    1. #include<cstdio>
    2. #include<cmath>
    3. using namespace std;
    4. const double eps=1e-5;
    5. double a,b,c,xx,yy;
    6. double f(double x){
    7.     return sqrt((x-xx)*(x-xx)+(a*x*x+b*x+c-yy)*(a*x*x+b*x+c-yy));
    8. }
    9. int main(){
    10.     scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&xx,&yy);
    11.     double l=-200,r=200;
    12.     while(r-l>eps){
    13.         double lm=l+(r-l)/3,rm=r-(r-l)/3;
    14.         if(f(lm)<f(rm)) r=rm;
    15.         else l=lm;
    16.     }
    17.     printf("%.3lf\n",f(l));
    18.     return 0;
    19. }

    例题:

    圆覆盖问题

    给定二维坐标图上若干个点, 求出最小能包含所有点的圆半径.

    观察发现, 如果不考虑y坐标, 只考虑x坐标, 假设我们的答案是m, 如果m 往左移, 或右移, 答案都会增大, 不会减少, 因为m已经是最优质的. 我们发现他是一个单峰值函数. 可以考虑3分解法.

    对于y坐标同理.

    现在唯一需要考虑的点是, 最优值的y 所构造出的最优质的x, 是不是就是全局最优?

    这是正确的. 因为这个关系是一个三维关系, x 不变 会产生一个f(y)的函数

    随着不同的x 产生, 会有这样一个图.

     反正就是随着x的增大, 这个图形就像是一个往里凹的腕一样. 当找到y的最优值, 再找x的最优质, 必然是最低点.

    学过偏微分就明白了.

    传送带

    AB 之间存在一个最优点, 只要离这个点越远, 时间增加的越多.

    同理 CD野存在.

    所以我们可以三分AB 之间的一个最优点E, 和三分CD之间的最优点F. 就可以找到答案了.

    f(E, F) = dis(A, E)/p + dis(F, D) / q + dis(E, F) / r

    三分套三分的一道题目

    01分数规划

     二分答案, 进行公示移项, 试错.

    小咪买东西

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define int long long
    4. int n, k;
    5. struct node{
    6.     int c, v, tmp;
    7. }a[10000000];
    8. bool cmp(node a, node b){
    9.     return a.tmp > b.tmp;
    10. }
    11. bool check(int x){
    12.     for(int i = 1; i <= n; i++){
    13.         a[i].tmp = a[i].v - a[i].c * x;
    14.     }
    15.     sort(a + 1, a + 1 + n, cmp);
    16.     int sum = 0;
    17.     for(int i = 1; i <= k; i++){
    18.         sum += a[i].tmp;
    19.     }
    20.     return sum >= 0;
    21. }
    22. signed main(){
    23.     int T;
    24.     cin >> T;
    25.     while(T--){
    26.         cin >> n >> k;
    27.         for(int i = 1; i <= n; i++){
    28.             cin >> a[i].c >> a[i].v;
    29.         }
    30.         int ans = 0;
    31.         int l = 1, r = 1e8 + 1000;
    32.         while(l <= r){
    33.             int mid = (l + r) / 2;
    34.             if(check(mid)){
    35.                 l = mid + 1;
    36.                 ans = mid;
    37.             }else{
    38.                 r = mid - 1;
    39.             }
    40.         }
    41.         cout << ans << endl;
    42.     }
    43.     return 0;
    44. }

    [USACO 2009 Dec S]Music Notes

    二分答案

    題目說時間從0開始累積, 會彈奏某一個音符b次, 也就是b秒.

    然後題目問某一個時間點彈到哪個音符.

    其實不難, 由於彈奏是一個累積的數組, 我們先求前綴和. 然後, 每一個前綴和代表彈第bi個音符的時候的時間是多少. 

    題目給了一個時間點t, 也就是說我們在這個前綴和中找出第一個大於或等於t的時間點中的索引就是答案的音符.

    1. #include<iostream>
    2. #include<algorithm>
    3. using namespace std;
    4. int main(){
    5.     int n, q;
    6.     cin >> n >> q;
    7.     int b[n + 1];
    8.     b[0] = 0;
    9.     for(int i = 1; i <= n; i++){
    10.         cin >> b[i];
    11.         b[i] = b[i - 1] + b[i];
    12.     }
    13.     while(q--){
    14.         int x;
    15.         cin >> x;
    16.         cout << (upper_bound(b + 1, b + 1 + n, x) - b) << endl;
    17.     }
    18.     return 0;
    19. }

    完全平方数(好問題!!!!)

    由於10億開方只有30000多, 我們大可以創建一個數組, 把1 到30000全部放在裡面.

    由於裡面全部都是實數, 所以每一個數字他的2次方都是完全平方數. 因此我們只需要找到 根號L到根號R之間有多少個數字就可以了. 最簡單的方法就是找第一個小於或等於根號L的數字, 和 第一個大於或等於根號R的地方, 相減就是完全平方數的數量了

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. const int N =31625;
    4. int a[N];
    5. int main()
    6. {
    7.     for(int i=0;i<N;++i)a[i]=i;
    8.     int n,l,r;
    9.     cin>>n;
    10.     while(n--){
    11.         cin>>l>>r;
    12.         int L=0,R=N;
    13.         L=lower_bound(a,a+N,sqrt(l))-a;
    14.         R=upper_bound(a,a+N,sqrt(r))-a;
    15.         cout<<max(R-L,0)<<endl;
    16.     }
    17.     return 0;
    18. }

    [USACO 2010 Feb S]Chocolate Eating

    我們二分一個每天最大可以保持的快樂值.

    拿到這個值我們就去check 到底可不可以保持.

    由於每天都會快樂減半, 所以一旦我們發現快樂值低於二分出來的x, 我們就不斷吃巧克力直到快樂水平達到或超過x. 

    由於巧克力的數量有限, 一旦發現巧克力吃完了但還是無法達到x水平, 證明這個x 是不可能成為合法的快樂值的.

    由於答案要我們同時輸出, 到底哪一天吃了哪些巧克力, 我們可以在吃巧克力讓快樂水平回到x的時候跟新一個答案 數組.

    1. #include <iostream>
    2.  
    3. using namespace std;
    4.  
    5. typedef long long LL;
    6. const int N = 1e6 + 10;
    7.  
    8. int n, d;
    9. LL level;
    10. LL a[N], c[N];
    11.  
    12. bool check(LL x)
    13. {
    14.     LL sum = 0, t = 0;
    15.     for(int i = 1; i <= d; i ++)
    16.     {
    17.         while(sum < x) 
    18.         {
    19.             sum += a[++t];
    20.             if(t > n) return false;
    21.             if(x == level) c[t] = i;
    22.         }
    23.         sum /= 2;
    24.     }
    25.      
    26.     return true;
    27. }
    28.  
    29. int main()
    30. {
    31.     cin >> n >> d;
    32.     for(int i = 1; i <= n; i ++) cin >> a[i];
    33.      
    34.     LL l = 0, r = 1e11;
    35.     LL ans = 0;
    36.     while(l <= r)
    37.     {
    38.         LL mid = l + r + 1 >> 1;
    39.         if(!check(mid)) r = mid - 1;
    40.         else{ l = mid + 1;
    41.             ans = mid;}
    42.     }
    43.      
    44.     level = ans;
    45.     check(level);
    46.     cout << level << endl;
    47.     for(int i = 1; i <= n; i ++)
    48.     {
    49.         if(c[i]) cout << c[i] << endl;
    50.         else cout << d << endl;
    51.     }
    52.          
    53.     return 0;
    54. }

    [NOIP2015]跳石头

    直接二分這個最短距離, 我們要讓所有距離都大於或等於這個距離. 

    實現方面就是, 我們要怎麼算這個用了多少次移動機會, 還有怎麼去移動呢?

    我們發現他所給的石頭距離是一個前綴和. 全部都是從起點到某個石頭的距離, 而且還是順序給出.

    這樣的話, 我們就可以用O(1)的時候直接把兩個點相減直接算到兩點的距離, 假設你把兩點中間的點都刪掉了, 是不會影響從a 點 到b 點的總距離的.只會影響最短距離.

    所以直接一個for 循環, 只要發現最後一次記錄的點 和當前點匹配的時候發現距離少於二分枚舉出來的點, 就直接用一個counter 計算移動次數 + 1. 如果比二分枚舉的x 要大 就直接跟新最後一詞出現的點.

    1. #include<iostream>
    2. using namespace std;
    3. int dis, n, m, a[1000000];
    4. bool check(int x){
    5.     int lastt = a[0];
    6.     int cnt = 0;
    7.     for(int i = 1; i <= n; i++){
    8.         if(a[i] - lastt < x){
    9.             cnt++;
    10.         }else{
    11.             lastt = a[i];
    12.         }
    13.     }
    14.     return cnt <= m && cnt <= n;
    15. }
    16. void work(){
    17.     a[0] =0;
    18.     cin >> dis >> n >> m;
    19.     for(int i = 1; i <= n; i++){
    20.         int y;
    21.         cin >> a[i];
    22.     }
    23.     int l = 0, r = dis;
    24.     int ans = 0;
    25.     while(l <= r){
    26.         int mid = (l + r) / 2;
    27.         if(check(mid)){
    28.             l = mid + 1;
    29.             ans = mid;
    30.         }else{
    31.             r = mid - 1;
    32.         }
    33.     }
    34.     cout << ans << endl;
    35. }
    36. int main(){
    37.     work();
    38.     return 0;
    39. }

    [USACO 2017 Dec P]Greedy Gift Takers

    我們發現如果第i頭牛不能拿到禮物,他後面的所有牛都不可能拿到禮物. 

    這裡具有11110000 這樣的單調性. 所以可以利用二分進行搜索最後一個出現可行的位置.

    也就是我們二分出來的x 是可以拿到禮物的牛的總數量.

    如何判斷是不是合法呢?

    我們發現如果在從0 到i 這個位置之間, 如果有多于i頭牛的數量, 那麼就會出現無限循環了, 有牛出隊, 再從新進隊, 並且位置就在原來的位置.

    最簡單的檢查方法就是, 我們直接用一個sum 記錄 在x 之前多少頭牛. 假設 我們已經知道每頭牛將會排在哪個位置, 我們就把0 到 x 的每個位置 會出現的牛的數量加起來, 如果超過他們所在的索引, 那麼就是犯法的. 原因是 在 x 前 你要讓他的和大於x, 只有當某個牛他會進隊的位置剛剛好在x 之前, 那麼就很明顯, 會開始一個循環.

    由於牛所排的位置, 是從尾巴數過來的, 所以我們要提前做一個處理, 把牛會排的位置變成從頭數起會排在哪.

    1. #include<iostream>
    2. #include<cstring>
    3. using namespace std;
    4. int n, a[100000];
    5. bool check(int mid){
    6.     int s[1000000];
    7.     memset(s, 0, sizeof(s));
    8.     for(int i = 1; i< mid; i++){
    9.         s[a[i]]++;
    10.     }
    11.     int sum = 0;
    12.     for(int i = 1; i < mid; i++){
    13.         sum+= s[i];
    14.         if(sum >= i)return 1;
    15.     }
    16.     return 0;
    17. }
    18. int main(){
    19.     cin >> n;
    20.     for(int i = 1; i <= n; i++){
    21.         cin >> a[i];
    22.         a[i] = n - a[i];
    23.     }
    24.     int l  =0, r = n;
    25.     while(l < r){
    26.         int mid = l + r + 1>> 1;
    27.         if(check(mid)){
    28.             r = mid - 1;
    29.         }else{
    30.             l = mid;
    31.         }
    32.     }
    33.     cout << n - r << endl;
    34.     return 0;
    35. }

    华华给月月准备礼物

    由於高於某個長度之後,的答案都是不可能的, 就是11110000 二分.

    所以我們直接二分可能的長度, 然後看看到底能不能切出指定數量 k.

    1. #include<iostream>
    2. using namespace std;
    3. int n, k;
    4. int w[300000];
    5. bool check(int mid){
    6.     int cnt =  0;
    7.     for(int i = 1; i <= n; i++){
    8.         cnt += w[i]/mid;
    9.     }
    10.     return cnt >= k;
    11. }
    12. int main(){
    13.     cin >> n >> k;
    14.     for(int i = 1; i <= n; i++){
    15.         cin >> w[i];
    16.     }
    17.     int l = 1, r = 2e9;
    18.     while(l <= r){
    19.         long long mid = l + r >> 1;
    20.         if(check(mid)){
    21.             l = mid + 1;
    22.         }else{
    23.             r = mid - 1;
    24.         }
    25.     }
    26.     cout << l - 1<< endl;
    27.     return 0;
    28. }

    [NOIP2011]聪明的质监员 (复习用)

    题目的公式是跟你说, Y = 某一个区间中, 只计算 那些 重量比 你所选的重量W 要重的矿产的价值和.

    价值和的公式 为 累积的数量 * 累积的价值.

    所以我们需要有数量前缀和, 和 价值前缀和, 并且 这些前缀和都是把 重量 比W小的剔除了的.

    然后我们二分 W.

    这里你会发现 当W 越小, 符合条件的矿产越多, 计算出来的价值和会越大, 所以当你发现价值和比S大了, 你就把 W 变大, 反之亦然.

    1. #include<bits/stdc++.h>
    2. #include<cstring>
    3. using namespace std;
    4. long long n, m, s;
    5. long long w[300000], v[300000];
    6. long long cnt[300000], sum[3000000];
    7. struct node{
    8.     int l, r;
    9. }a[3000000];
    10. long long check(int mid){
    11.     //cal the prefix sum and cnt
    12.  
    13.     for(int i = 1; i <= n; i++){
    14.         if(w[i] >= mid){
    15.             cnt[i] = cnt[i - 1] + 1;
    16.             sum[i] = sum[i - 1] + v[i];
    17.         }else{
    18.             cnt[i] = cnt[i - 1];
    19.             sum[i] = sum[i - 1];
    20.         }
    21.     }
    22.     long long res = 0;
    23.     for(int i = 1; i <= m; i++){
    24.         res += (cnt[a[i].r] - cnt[a[i].l - 1])*(sum[a[i].r] - sum[a[i].l - 1]);
    25.     }
    26.     return res;
    27. }
    28. int main(){
    29.     cin >> n >> m >> s;
    30.     for(int i = 1; i <= n; i++){
    31.         cin >> w[i] >> v[i];
    32.     }
    33.     for(int i = 1; i <= m; i++){
    34.         cin >> a[i].l >> a[i].r;
    35.     }
    36.     int l = 1, r = 1e9;
    37.     int ans = 0;
    38.     while(l <= r){
    39.         int mid = l + r >> 1;
    40.         if(check(mid) >= s){
    41.             l = mid + 1;
    42.         }else{
    43.             r = mid - 1;
    44.         }
    45.     }
    46.     cout << min(abs(check(r) - s), abs(check(r + 1) - s))<< endl;
    47.     return 0;
    48. }

  • 相关阅读:
    SQL语句性能优化
    分享几个实用且高效的EF Core扩展类库，提高开发效率！
    嘉立创EDA的一些使用技巧
    将 LevelDB 系统放置在内存（全内存架构）
    js截取字符串中某个字符前后的内容
    【亲测有效】3步实现 微信小程序内接入小程序客服，网页端客服工具与移动端小程序客服工具使用方法，使用入口，并设置当前客服状态
    208. 实现 Trie (前缀树)
    网页设计前端作品（大一）HTML+CSS
    P4302 [SCOI2003]字符串折叠 (区间DP)
    httpd和cgi 的使用
  • 原文地址：https://blog.csdn.net/weixin_58286631/article/details/125356656