<div id="7x91n"></div>
    <progress id="7x91n"><tr id="7x91n"><ruby id="7x91n"></ruby></tr></progress>

    <em id="7x91n"></em>
      <progress id="7x91n"></progress>

      <dl id="7x91n"><ins id="7x91n"></ins></dl>

          <div id="7x91n"></div>

          <dl id="7x91n"></dl>

          <dl id="7x91n"><ins id="7x91n"><thead id="7x91n"></thead></ins></dl>

            <div id="7x91n"><tr id="7x91n"></tr></div>

            <div id="7x91n"></div>
            <div id="7x91n"></div>
            <dl id="7x91n"></dl><dl id="7x91n"><ol id="7x91n"></ol></dl>
            首頁 > 其他 > 詳細

            POJ-3061 Subsequence 二分或尺取

            時間:2018-09-23 11:01:01      閱讀:35      評論:0      收藏:0      [點我收藏+]

            標簽:printf   重復   pac   include   題解   pro   cstring   判斷   ron   

            題面

            題意:給你一個長度為n(n<100000)的數組,讓你找到一個最短的連續子序列,使得子序列的和>=m  (m<1e9)

            題解: 1 顯然我們我們可以二分答案,然后利用前綴和判斷是否可行,這樣是O(nlgn)的   注意沒有答案 ans輸出0

             

             1 #include<cstdio>
             2 #include<cstdlib>
             3 #include<iostream>
             4 #include<cstring>
             5 using namespace std;
             6 int T,n,m,a[100005],l,r,ans;
             7 int check(int x)
             8 {
             9     for (int i=1;i<=n-x+1;i++)
            10     {
            11         if (a[i+x-1]-a[i-1]>=m) return 1;
            12      }
            13      return 0;
            14 }
            15 int main()
            16 {
            17     scanf("%d",&T);
            18     while (T--)
            19     {
            20         memset(a,0,sizeof(a));
            21         scanf("%d%d",&n,&m);
            22         for (int i=1;i<=n;i++) 
            23         {
            24             scanf("%d",&a[i]);
            25             a[i]+=a[i-1]; 
            26         }
            27         l=1;r=n;ans=0;
            28         while (l<=r)
            29         {
            30             int mid=(l+r)/2;
            31             if (check(mid)) 
            32             {
            33                 ans=mid;
            34                 r=mid-1;
            35             }else l=mid+1;
            36         }
            37         printf("%d\n",ans);
            38     } 
            39  } 

              2 還是一道尺取的裸題,先取前x個數(r++),直到大于m,此時減去該區間最前面的一個數(收縮 l++),再次判斷是否大于S,重復操作,直至r==n或取得的區間無法大于S 停止

             1 #include<cstdio>
             2 #include<cstdlib>
             3 #include<iostream>
             4 #include<cstring>
             5 using namespace std;
             6 int sum,T,n,m,a[100005],l,r,ans;
             7 int check(int x)
             8 {
             9     for (int i=1;i<=n-x+1;i++)
            10     {
            11         if (a[i+x-1]-a[i-1]>=m) return 1;
            12      }
            13      return 0;
            14 }
            15 int main()
            16 {
            17     scanf("%d",&T);
            18     while (T--)
            19     {
            20         memset(a,0,sizeof(a));
            21         scanf("%d%d",&n,&m);
            22         for (int i=1;i<=n;i++) scanf("%d",&a[i]);
            23         
            24         ans=n+1;l=1;r=1;sum=0;
            25         while (1)
            26         {
            27             while (r<=n && sum<m)
            28             {
            29                 sum+=a[r];
            30                 r++;
            31             }
            32             if (sum<m) break;else
            33             {
            34                 ans=min(ans,r-l);
            35                 sum-=a[l];
            36                 l++;
            37             } 
            38         }
            39         if (ans!=n+1) printf("%d\n",ans);else printf("0\n");
            40     } 
            41  } 

             

            POJ-3061 Subsequence 二分或尺取

            標簽:printf   重復   pac   include   題解   pro   cstring   判斷   ron   

            原文:https://www.cnblogs.com/qywhy/p/9691705.html

            (0)
            (0)
               
            舉報
            評論 一句話評論(0
            0條  
            登錄后才能評論!
            ? 2014 bubuko.com 版權所有 魯ICP備09046678號-4
            打開技術之扣,分享程序人生!
                         

            魯公網安備 37021202000002號

            福建省餐饮许可现场