• <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年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿

            文章分類

            文章檔案

            搜索

            最新評論

            国产成人无码精品久久久久免费 | 综合久久一区二区三区| 国产精品成人99久久久久| 香蕉aa三级久久毛片| 久久久久亚洲精品日久生情| 国产精品无码久久久久久| 久久国产视频99电影| 无码超乳爆乳中文字幕久久| 亚洲精品高清久久| 亚洲国产精品无码久久久不卡| 国产免费久久精品丫丫| 亚洲色大成网站WWW久久九九| 国产高潮国产高潮久久久91| 国内精品伊人久久久久妇| segui久久国产精品| 精品免费久久久久久久| 亚洲欧美日韩精品久久亚洲区| 久久国产乱子伦精品免费强| 久久久久人妻一区二区三区| 久久综合成人网| 久久久久国色AV免费看图片| 久久99毛片免费观看不卡| 久久精品亚洲精品国产色婷| 欧美国产精品久久高清| 91精品免费久久久久久久久| 日韩精品久久久久久| 久久99亚洲网美利坚合众国| 色诱久久久久综合网ywww | 久久精品国产精品亚洲毛片| 91麻豆国产精品91久久久| 午夜精品久久久久久影视777| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 2021久久精品国产99国产精品| 久久这里的只有是精品23| 欧美久久一级内射wwwwww.| 久久综合五月丁香久久激情| 久久久久久久综合日本| 久久精品18| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 久久人人爽人爽人人爽av| 日批日出水久久亚洲精品tv|