BUPT OJ180 大牛们的午饭

本文主要是介绍BUPT OJ180 大牛们的午饭，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

大家都知道ACM比赛有提供午饭的传统,正好最近学校要举办程序设计竞赛，可是ACM大牛们都去打比赛去了.只剩下弱菜Saerdna一个人负责大牛们的午饭.因为负责送那么多大牛的午饭是一件很累的活，所以Saerdna当然希望每位大牛都吃得少一点，最好都不吃。。。。但是不送午饭又说不过去，所以对于每个大牛，Saerdna都会送去一份午饭。
因为每个大牛都有一个大牛值，所以大牛之间都会暗自较劲，为了不让大牛们起冲突，Saerdna送去的午饭必需保证相邻两个大牛之间存在以下关系,大牛值大的大牛得到的午饭比大牛值小的大牛要多。

输入格式

一开始是一个数字T(T<=10)表示数据组数
接下来T行，每行是一个数n.(n<=10^6)
接下来一行有n个数，表示每个大牛的大牛值。

输出格式

Saerdna最少需要送多少饭。

输入样例

输出样例

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

这篇关于BUPT OJ180 大牛们的午饭的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！