题目描述
大家都知道ACM比赛有提供午饭的传统,正好最近学校要举办程序设计竞赛，可是ACM大牛们都去打比赛去了.只剩下弱菜Saerdna一个人负责大牛们的午饭.因为负责送那么多大牛的午饭是一件很累的活，所以Saerdna当然希望每位大牛都吃得少一点，最好都不吃。。。。但是不送午饭又说不过去，所以对于每个大牛，Saerdna都会送去一份午饭。
因为每个大牛都有一个大牛值，所以大牛之间都会暗自较劲，为了不让大牛们起冲突，Saerdna送去的午饭必需保证相邻两个大牛之间存在以下关系,大牛值大的大牛得到的午饭比大牛值小的大牛要多。
输入格式
一开始是一个数字T(T<=10)表示数据组数
接下来T行，每行是一个数n.(n<=10^6)
接下来一行有n个数，表示每个大牛的大牛值。
输出格式
Saerdna最少需要送多少饭。
输入样例
2
3
1 2 3
4
3 1 2 2输出样例
6
6热身赛的题, 从前往后扫一遍, 从后往前扫一遍, 然后取最大值. 时空复杂度均为O(N)
证明很简单, 即从一个方向扫可以得到所有此方向递增的序列, 并且扫得结果满足左邻居/右邻居所需条件的最小值 所以扫两次后所得最大值即是最小同时满足左右邻居的(午饭)值
这题和以前在leetcode上做过的某道candy几乎一模一样，可以实现O(N)时间和O(1)空间, 而且可以实现只扫一遍得出结果. 反正只要过了就行, 这个方法以后再讨论吧
/*
USER_ID: test#birdstorm
PROBLEM: 180
SUBMISSION_TIME: 2014-03-08 01:00:03
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MAX(x,y) (x)>(y)?(x):(y)
#define For(i,m,n) for(i=m;i<n;i++)int a[1000005], b[1000005], c[1000005];main()
{int t, n, i, j, sum, x;scanf("%d",&t);while(t--){scanf("%d",&n); sum=0;For(i,0,n) b[i]=c[i]=1;For(i,0,n) scanf("%d",&a[i]);For(i,1,n){if(a[i-1]<a[i]) b[i]=b[i-1]+1;else b[i]=1;}for(i=n-2;i>=0;i--){if(a[i+1]<a[i]) c[i]=c[i+1]+1;else c[i]=1;}For(i,0,n) sum+=MAX(b[i],c[i]);printf("%d\n",sum);}return 0;
}
================更新: (2014/03/17)================
这两天有同学问我这题, 于是又看了一遍, 然后模仿leetcode上提到的做法重写了一个O(N)时间 O(1)空间的代码
主要是学习了这种只扫描一遍以及不额外分配空间的方法, 还是收获很大的.
此方法可以只需要得知当前项和前一项就能推出当前午餐值, 而不必存储整个序列.
主体思路是:
读入当前项后进行以下操作和判断
1)严格单调下降: 存储除峰值外当前严格单调下降序列长度以及峰值时的午餐值, 此严格下降单调序列所有午餐值+1.
要注意当峰值与此序列长度相等时, 需要扩充序列长度, 把峰值也包含进单调下降序列, 整个序列午餐值全部+1.
2)严格单调上升: 只需要令当前项的午餐值是前一项的午餐值+1即可.
3)当前项与前一项的午餐值相等时, 则当前项午餐值=1.
这样写出的代码也如同思路一样, 简洁易懂.
/*
USER_ID: test#birdstorm
PROBLEM: 180
SUBMISSION_TIME: 2014-03-17 16:59:00
*/
#include <stdio.h>
#define For(i,m,n) for(i=(m);i<(n);i++)main()
{int i, n, t, now, prev, nCnt;int nSeqLen, nPreCnt, nMaxCntInSeq;scanf("%d", &t);while(t--){scanf("%d%d", &n, &prev);nCnt=1; nSeqLen = 0; nMaxCntInSeq = nPreCnt = 1;For(i,1,n){scanf("%d", &now);if(now < prev){nSeqLen++;if(nMaxCntInSeq == nSeqLen) nSeqLen++;nCnt+= nSeqLen;nPreCnt = 1;}else{if(now > prev) nPreCnt++;else nPreCnt = 1;nCnt += nPreCnt;nSeqLen = 0;nMaxCntInSeq = nPreCnt;}prev=now;}printf("%d\n",nCnt);}return 0;
}