尺取法 刷题记录

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