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
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;
}