• <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

            導航

            統計

            常用鏈接

            留言簿

            文章分類

            文章檔案

            搜索

            最新評論

            亚洲色欲久久久久综合网| 久久精品国产亚洲AV久| 91精品日韩人妻无码久久不卡| 久久AV高清无码| 久久天天躁狠狠躁夜夜2020老熟妇 | 思思久久99热只有频精品66| 狠狠综合久久综合88亚洲| 99久久国产热无码精品免费| 精品久久久久久久久久中文字幕| 亚洲国产视频久久| 色综合色天天久久婷婷基地| 伊人久久大香线蕉综合5g| 人人狠狠综合久久亚洲婷婷| 色天使久久综合网天天| 国产精品免费久久久久电影网| 久久久久久精品免费看SSS| 久久精品国产99久久久香蕉| 亚洲欧美伊人久久综合一区二区| 久久久无码精品亚洲日韩软件| 久久精品国产亚洲av影院| 国内精品久久久久影院亚洲| 久久精品国产亚洲精品| 99久久伊人精品综合观看| 91久久婷婷国产综合精品青草| 国产69精品久久久久APP下载| 精品熟女少妇aⅴ免费久久| 精品久久久久久国产| 国产综合久久久久| 久久国产精品99精品国产| 天天躁日日躁狠狠久久| 久久99精品国产麻豆宅宅| 人妻无码精品久久亚瑟影视| 欧美一级久久久久久久大片| 精品多毛少妇人妻AV免费久久| 精品久久久久久久久中文字幕| 久久国产高潮流白浆免费观看| 99精品国产综合久久久久五月天 | 亚洲精品无码久久久久| 久久久久久精品无码人妻| 五月丁香综合激情六月久久| 久久综合九色综合网站|