• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            hdu3434

            題目來源: http://acm.hdu.edu.cn/showproblem.php?pid=3434 

            Sequence Adjustment

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 463    Accepted Submission(s): 144


            Problem Description
            Given a sequence consists of N integers. Each time you can choose a continuous subsequence and add 1 or minus 1 to the numbers in the subsequence .You task is to make all the numbers the same with
            the least tries. You should calculate the number of the least tries
            you needed and the number of different final sequences with the least tries.
             


             

            Input
            In the first line there is an integer T, indicates the number of test cases.(T<=30)
            In each case, the first line contain one integer N(1<=N<=10^6),
            the second line contain N integers and each integer in the sequence is between [1,10^9].
            There may be some blank lines between each case.
             


             

            Output
            For each test case , output “Case d: x y “ where d is the case number
            counted from one, x is the number of the least tries you need and y
            is the number of different final sequences with the least tries.
             


             

            Sample Input
            2 2 2 4 6 1 1 1 2 2 2
             


             

            Sample Output
            Case 1: 2 3 Case 2: 1 2
            Hint
            In sample 1, we can add 1 twice at index 1 to get {4,4},or minus 1 twice at index 2 to get {2,2}, or we can add 1 once at index 1 and minus 1 once at index 2 to get {3,3}. So there are three different final sequences.
             


             

            Author
            wzc1989
             


             

            Source


            /*
            更詳盡的解題報告見:
            http://hi.baidu.com/liwang112358/blog/item/3dac7e566f300f55d0090679.html 
            */
            #include <stdio.h>
            #include <memory>
            #include <iostream>
            #include <algorithm>
            #include <cstring>
            #include <vector>
            #include <map>
            #include <cmath>
            #include <set>
            #include <queue>
            #include <time.h>
            #include <limits>
            using namespace std;
            #define N 1000005
            #define ll long long
            #define ABS(a) (a > 0 ? a : -a)
            ll a[N], p[N];
            int main(){
            #ifndef ONLINE_JUDGE
             freopen("in.txt", "r", stdin);
             //freopen("out.txt", "w", stdout);
            #endif
             int t, n, ca;
             ca = a[0] = p[0] = p[1] = 0;
             scanf("%d", &t);
             while(t--){
              scanf("%d", &n);
              int i, j;
              ll sum, ans;
              for(i = 1; i <= n; i++) scanf("%d", a+i);
              for(i = 2, j = 1; i <= n; i++){
               if(a[i] != a[j]){
                a[++j] = a[i];
                p[j] = a[j] - a[j - 1];
               }
              }
              n = j;
              ans = sum = 0;
              for(i = 2; i <= n; i++){
               if(p[i] * sum < 0) ans += min(ABS(sum), ABS(p[i]));
               sum += p[i];
              }
              sum = ABS(sum);
              ans += sum;
              //printf("Case %d: %lld %lld\n", ++ca, ans, sum + 1);
              printf("Case %d: %I64d %I64d\n", ++ca, ans, sum + 1);
             }
             return 0;
            }

             

             

            posted on 2011-01-21 16:01 tw 閱讀(253) 評論(0)  編輯 收藏 引用 所屬分類: HDU題解

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            文章分類

            文章檔案

            搜索

            最新評論

            精品国产91久久久久久久a| 91精品国产91热久久久久福利| 久久久久无码中| 亚洲国产精品无码久久九九| 亚洲国产天堂久久久久久| 国产精品亚洲综合久久| 亚洲国产另类久久久精品黑人 | 无码超乳爆乳中文字幕久久| 久久综合狠狠综合久久| 日本免费一区二区久久人人澡 | 久久久久99精品成人片| 精品久久久久成人码免费动漫| 麻豆亚洲AV永久无码精品久久| 天天综合久久久网| 亚洲国产精品无码久久98| 国产精品久久久99| 亚洲国产精品成人久久| 免费一级欧美大片久久网| 久久久久亚洲精品无码蜜桃| 欧美久久一级内射wwwwww.| 久久人人爽人人爽人人AV东京热| 久久综合久久综合九色| 丁香色欲久久久久久综合网| 精品无码久久久久久国产| 久久精品黄AA片一区二区三区 | 97精品伊人久久大香线蕉| 国产成人精品久久一区二区三区av | 久久婷婷午色综合夜啪| 久久www免费人成看国产片| 国产成人精品久久免费动漫| 久久福利资源国产精品999| 久久综合狠狠综合久久97色| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 欧美色综合久久久久久| 久久99久久成人免费播放| 久久er热视频在这里精品| 久久久一本精品99久久精品88| 亚洲国产精品成人久久| 狠狠色婷婷久久一区二区三区| 性做久久久久久久| 久久久国产精品亚洲一区|