首页 > 其他 > 详细

尺取法 刷题记录

时间:2019-11-20 09:12:57      阅读:90      评论:0      收藏:0      [点我收藏+]

POJ3061Subsequence

  • 模板题,给出n个数和S,求长度最小的区间,使得区间和不小于S
  • 代码:
    技术分享图片
     1 #include <cstdio>
     2 #include <iostream>
     3 #include <algorithm>
     4 #define nmax 100010
     5 
     6 using namespace std;
     7 int a[nmax];
     8 int n, s;
     9 
    10 bool f(int& p, int& sum){
    11     while (sum<s && p<n) sum += a[++p];
    12     return (p==n && sum<s); 
    13 }
    14 
    15 int main(){
    16     int cas;
    17     cin >> cas;
    18     while(cas--){
    19         scanf("%d%d", &n, &s);
    20         for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    21         int p=0, sum=0;
    22         if( f(p, sum) ) { printf("0\n"); continue; }
    23         int r=p, ans=p;
    24         for (int l=2; l<=n; l++) {
    25             sum -= a[l-1];
    26             if( f(r, sum) ) break;
    27             ans = min(ans, r-l+1);
    28         }
    29         printf("%d\n", ans);
    30     }
    31     return 0;
    32 }
    ( ̄┰ ̄*)

     

POJ2566Bound Found

  • 妙哇
  • 题意:求一段区间,使得区间和的绝对值最接近T
  • 做法:尺取法一定要答案递增,那考虑先求出前缀和,然后前缀和排序,这样如果s[r]-s[l]小于T就让r增加,因为绝对值还能更小,否则r结束增加
  • 注意不要写成s[r]-s[l-1]了,这样会出现负数
  • 调了两天的我菜的真实,我的码力基本告别ACM了
  • 技术分享图片
     1 #include <cstdio>
     2 #include <iostream>
     3 #include <algorithm>
     4 #define nmax 100010 
     5 #define f(l,r) (s[r].first-s[l].first)
     6 
     7 using namespace std;
     8 typedef long long ll;
     9 ll n, k, t;
    10 ll a[nmax];
    11 pair<ll,int> s[nmax];
    12 const ll inf = 1e15;//这里只开到1e9会wa
    13 int r, ansl, ansr, l;
    14 ll ans, tmp=inf;
    15 
    16 inline void newa(int l, int r) {
    17     if( abs( t-f(l,r) ) < tmp ) {
    18         tmp = abs( t-f(l,r) );
    19         ansl = s[l].second;
    20         ansr = s[r].second;
    21         ans = f(l,r);
    22     }
    23 }
    24 
    25 void solve(){
    26     tmp = inf; r=1;
    27     for (l=0; l<n; l++) {
    28         if(r<=l) r=l+1;
    29         while(f(l,r)<t && r<=n){
    30             newa(l,r);
    31             if(f(l,r)==t) break;
    32             r++;
    33         }
    34         if(r>n) break;
    35         newa(l,r);
    36     }
    37     if(ansl>ansr) swap(ansl,ansr);
    38 }
    39 
    40 int main(){
    41     while(scanf("%I64d%I64d", &n, &k)!=EOF && (n||k) ){
    42         s[0].first = s[0].second = 0;
    43         for (int i=1; i<=n; i++) {
    44             scanf("%lld", &a[i]);
    45             s[i].first = s[i-1].first + a[i];
    46             s[i].second = i;
    47         }
    48         sort(s, s+n+1);
    49         while(k--){
    50             scanf("%I64d", &t);
    51             solve();
    52             printf("%I64d %d %d\n", ans, ansl+1, ansr);
    53         }
    54     }
    55     return 0;
    56 }
    ??

     

尺取法 刷题记录

原文:https://www.cnblogs.com/jiecaoer/p/11894845.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!