2018亚洲区预选赛北京赛站网络赛 D.80 Days 尺取-白红宇

2018亚洲区预选赛北京赛站网络赛 D.80 Days 尺取

阅读量：7071 次

发布时间：2019-06-28

本文共 5446 字，大约阅读时间需要 18 分钟。

题意:你带着K元要去n个城市,这n个城市是环形的,你可以选择任意一个起点,然后顺时针走,对于每个城市,到达时可以获得a元,但是从这里离开又需要花费b元,问你能否找到一个起点(输出花钱最少的那个),使得你能够走完一圈,不能输出-1

题解:首先对于环形问题,先把数组复制一次,现在从每个起点开始,满足条件的点就肯定可以进队,其实我们要求的一个i满足,从i到n+i的所有前缀和最小值一定要大于K,因为对于1个i只会进队一次出队一次,所以尺取一下

(我们一路判断的就是,带着K元能不能加上这段区间>=0,不能的话起点就要顺延,同时终点也顺延,每次只改变头首2个元素)

1 #include
     
       2 #define N 2000010  3 using namespace std; 4 int T,ans,n,m,cnt,b[N],a[N],c[N]; 5 int main() 6 { 7     scanf("%d",&T); 8     while (T--)  9     {10         scanf("%d%d",&n,&m);11         for (int i=1;i<=n;i++) scanf("%d",&a[i]);12         for (int i=1;i<=n;i++) scanf("%d",&b[i]);13         for (int i=1;i<=n;i++)14         {15             c[i]=a[i]-b[i];16             c[i+n]=c[i];17         }18         int l=1,r=1;19         long long ans=0;20         while (l<=n && r-l+1<=n)21         {    22             ans+=c[r];23             r++;24             while (ans+m<0) 25             {26                 ans-=c[l];27                 l++;28             }29         }30         if (l>n) printf("-1\n");else printf("%d\n",l);31     }32     return 0;33 }

比赛时,队友为了实现类似想法,却苦于没听过尺取(我也没听过),和不是很能确定a[i]和b[i]是否能统一的问题,大力码的2种。

1 #include
      
        2 using namespace std; 3 #define mem(a,i) memset(a,i,sizeof(a)) 4 #define rep(i,a,b) for(int i=a;i<=b;++i) 5 #define per(i,a,b) for(int i=a;i>=b;--i) 6 #define lowbit(x) (x&-x) 7 #define pb push_back 8 #define mp make_pair 9 #define fi first10 #define se second11 typedef long long ll;12 typedef pair
       
         pii;13 const ll INF=0x3f3f3f3f3f3f3f3f;14 const int maxn=1e6+5;15 ll a[maxn*2];16 ll b[maxn*2];17 int n;18 ll sum;19 int main() {20     int caseCnt;21     scanf("%d",&caseCnt);22     while(caseCnt--) {23         scanf("%d%lld",&n,&sum);24         rep(i,0,n-1) scanf("%lld",&a[i]);25         rep(i,n,2*n-1) a[i]=a[i-n];26         rep(i,0,n-1) scanf("%lld",&b[i]);27         rep(i,n,2*n-1) b[i]=b[i-n];28         int l=0;29         while(l
        
         =0) {31                 break;32             }33             l++;34         }35         if(l==n) puts("-1");36         else {37             int r=l+1;38             ll res=sum+a[l];39             ll temp=res;40             bool ok=false;41             while(r<2*n) {42                 if(r-l==n) temp=res-b[r-1];43                 else temp=min(res-b[r-1],res-b[r-1]+a[r]);44                 if(temp<0) break;45                 if(r-l==n) {46                     ok=true;47                     break;48                 }49                 res=res-b[r-1]+a[r];50                 r++;51             }52             if(ok) {53                 printf("%d\n",l+1);54                 continue;55             }56             int ans;57             while(l
         
          =0) {67                             break;68                         }69                         l++;70                     }71                     if(l==n) break;72                     r=l;73                     res=sum+a[l];74                 }75                 r=r+1;76                 while(r<2*n) {77                     if(r-l==n) temp=res-b[r-1];78                     else temp=min(res-b[r-1],res-b[r-1]+a[r]);79                     if(temp<0) break;80                     if(r-l==n) {81                         ans=l+1;82                         ok=true;83                         break;84                     }85                     res=res-b[r-1]+a[r];86                     r++;87                 }88                 if(ok) break;89             }90             if(!ok) puts("-1");91             else {92                 printf("%d\n",ans);93             }94         }95     }96     return 0;97 }

View Code

1 #include 
      
         2 #include 
       
          3 #include
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #include 
               
                 11 #include
                
                  12 #include
                 
                   13 #include
                   14 #include
                   
                     15 using namespace std; 16 long long a[2000050], b[2000050]; 17 int main() { 18 long long i, j, k, n, m, l, r, res, t, c, ans; 19 scanf("%lld", &t); 20 while (t--) 21 { 22 scanf("%lld%lld", &n, &c); 23 for (i = 0; i < n; i++) { 24 scanf("%lld", &a[i]); 25 a[n + i] = a[i]; 26 } 27 for (i = 0; i < n; i++) { 28 scanf("%lld", &b[i]); 29 b[n + i] = b[i]; 30 } 31 l = 0; 32 while (l < n&&c + a[l] < 0) 33 l++; 34 if (l == n) 35 { 36 printf("-1\n"); 37 continue; 38 } 39 r = l; res = c + a[l]; 40 bool ok = false; 41 while (l < n) 42 { 43 bool flag = false; 44 long long need = b[r]; 45 if (a[r + 1] < 0 && r + 1 != (n + l)) { 46 need -= a[r + 1]; 47 flag = true; 48 } 49 while (r < (n + l) && res >= need) 50 { 51 r++; 52 res = res - need; 53 if(!flag) 54 res = res + a[r]; 55 flag = false; 56 if (r == (n + l - 1)) { 57 need = b[r]; 58 flag = false; 59 } 60 else { 61 need = max(b[r], b[r] - a[r+1]); 62 if (a[r+1] < 0) 63 flag = true; 64 } 65 } 66 if (r == (l + n)) 67 { 68 ok = true; 69 ans = l; 70 break; 71 } 72 res = res - need; 73 r++; 74 while (l < r&&res + b[l] - a[l] < 0) { 75 res = res + b[l] - a[l]; 76 l++; 77 } 78 if (!flag) 79 res += a[r]; 80 if (l == r) 81 { 82 while (l < n&&c + a[l] < 0) 83 l++; 84 if (l == n) 85 { 86 break; 87 } 88 else 89 { 90 r = l; 91 res = c + a[l]; 92 } 93 } 94 else 95 { 96 res = res + b[l] - a[l]; 97 l++; 98 } 99 }100 if (ok)101 {102 printf("%lld\n", ans + 1);103 }104 else105 printf("-1\n");106 }107 }

View Code

转载于:https://www.cnblogs.com/qywhy/p/9692534.html

你可能感兴趣的文章