首页 > ACM题库 > HDU-杭电 > HDU 3434-Sequence Adjustment-数学相关-[解题报告]HOJ
2014
03-23

HDU 3434-Sequence Adjustment-数学相关-[解题报告]HOJ

Sequence Adjustment

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2
2
2 4
6
1 1 1 2 2 2

样例输出:

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.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define L 1000100
int a[L],b[L],p[L];
long long min(long long x,long long y)
{
    if (x<y) return x;
    return y;
}
int main()
{
    int T;
    int cas=1;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)  scanf("%d",&a[i]);

        int len=1;//缩
        b[len]=a[1];
        for(int i=2;i<=n;i++)  if(a[i]!=a[i-1])  b[++len]=a[i];

        p[1]=0;
        for(int i=2;i<=len;i++)  p[i]=b[i]-b[i-1];

        long long sum=0,ans=0;
        for(int i=2;i<=len;i++)
        {
            if(p[i]*sum<0)  ans+=min(abs(sum),abs(p[i]));
            sum+=p[i];
        }

        sum=abs(sum);
        ans+=sum;//处理单向的需要付出的代价
        printf("Case %d: %I64d %I64d\n",cas++,ans,sum+1);
    }
    return 0;
}
//这种我现在还是无法证明
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int A[1000005];
int main()
{
    int cas,r=1;
    scanf("%d",&cas);
    while(cas--)
    {
        int N;
        scanf("%d",&N);
        for(int i=0; i<N; i++)
            scanf("%d",&A[i]);
        long long a=0,b=0;
        for(int i=1; i<N; i++)
        {
            if (A[i]-A[i-1]>0) a+=A[i]-A[i-1];
            else b-=A[i]-A[i-1];
        }
        int Max = max(A[0],A[N-1]), Min = min(A[0],A[N-1]);
        printf("Case %d: %I64d %d\n",r++,(a>b?a:b),Max-Min+1);
    }
}

参考:http://blog.csdn.net/hqd_acm/article/details/6581905


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。