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

            導航

            統計

            常用鏈接

            留言簿

            文章分類

            文章檔案

            搜索

            最新評論

            jizzjizz国产精品久久| 国产成人精品久久一区二区三区| 国产成人无码精品久久久免费 | 色偷偷91久久综合噜噜噜噜| 色综合合久久天天给综看| 伊人久久大香线蕉av不卡| 青青草国产精品久久| 国产成人精品综合久久久| 97超级碰碰碰碰久久久久| 无码精品久久久久久人妻中字| 中文字幕亚洲综合久久2| 99久久精品国产一区二区| 国产成人综合久久久久久| 久久久噜噜噜久久中文福利| 久久人人爽人爽人人爽av| 久久青草国产精品一区| 亚洲va国产va天堂va久久| 日韩电影久久久被窝网| 国产高清国内精品福利99久久| 久久狠狠高潮亚洲精品| 久久久久久曰本AV免费免费| 久久精品二区| 久久国产精品偷99| 丁香久久婷婷国产午夜视频| 久久96国产精品久久久| 一本色道久久综合亚洲精品| 国内精品伊人久久久影院| 久久人搡人人玩人妻精品首页| 亚洲国产二区三区久久| 久久99精品国产麻豆宅宅| 精品九九久久国内精品| 2021久久精品国产99国产精品| 久久天天躁狠狠躁夜夜avapp| 亚洲国产精品无码久久SM | 久久精品无码一区二区app| 91久久香蕉国产熟女线看| 久久久久久久99精品免费观看| 精品久久久久久国产91| 色成年激情久久综合| 国产精品99久久久久久宅男| 久久精品国产精品亚洲人人|