2 xsxshxs2 xsxshxs2 于 2015.07.07 19:30 提问

一道题目,请大家帮帮忙,谢谢了

【问题描述】
  小山田心子是一只快乐的小白兔,某天她看到一座彩虹桥,彩虹桥长度为N,每个单位都有一个美观度,小山田心子一开始在单位1,并取走单位1的美观值,接下来她会在从下一格开始到N中选择一个最大美观度的单位跳过去(如果美观值相同取前面的),然后取走美观值,直到她走到N,请输出她取走的美观度之和。
【输入格式】
  第一行一个整数N(10<N<1000),接下来一行N个整数表示彩虹桥每个单位的美观度。
【输出格式】
  小山田心子取过的美观值之和。

【输入样例1】
  5
  5 4 3 2 1
【输出样例1】
  15

【输入样例2】
  10
  5 9 4 6 10 8 7 5 4 7
【输出样例2】
  37

【样例解释】
  样例1:(兔子一开始在单位1(取走美观度5),然后在2到5找最大,找到单位2的美观度4…一直找到单位N,美观度是15);
  样例2:(兔子先取单位1,在2到10中找最大找到单位5的美观度10,然后在6到10找最大找到单位6的美观度8,然后在7到10找最大找到单位7的美观度7,接下来在单位8到10找到单位10的美观度7,答案即为5+10+8+7+7=37)。

【数据范围】
  N=200000(注意这里)
其中一个 n=200000 的数据点 http://pan.baidu.com/s/1o6qrs2A
感谢大神

6个回答

hfut_wowo
hfut_wowo   2015.07.07 20:16
已采纳

虽然是从前往后跳,但是感觉求值应该从后来算。你看哈,从最后一位开始,肯定是可以取到的,然后将这位作为flag,向前搜索。如果比flag小,则略过,如果大于flag,则计入总和,并更新flag。如此往前搜索,直到第一位,当然第一位也计入总和。这样复杂度也就是O(1)。题主琢磨下是否可行?

hfut_wowo
hfut_wowo 代码给你发下面了
2 年多之前 回复
hfut_wowo
hfut_wowo 错了,样例
2 年多之前 回复
hfut_wowo
hfut_wowo 额,我C++不是很熟,你过不去的话程序应该有问题,我用php写了下,两个阳历都是没问题的。
2 年多之前 回复
xsxshxs2
xsxshxs2 回复wowo: 这样,第一个样例过不去
2 年多之前 回复
xsxshxs2
xsxshxs2 回复wowo: 这样,第一个样例过不去
2 年多之前 回复
xsxshxs2
xsxshxs2 回复wowo: #include<iostream> using namespace std; long long a[200000],n,b,t=0,flag=0; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; t+=a[n]; flag=a[n]; for(int c=n-1;c>=1;c--) { if(a[c]>=flag) { t+=a[c]; flag=a[c]; } } t+=a[1]; cout<<t; }
2 年多之前 回复
xsxshxs2
xsxshxs2 回复wowo: 你好,还在吗
2 年多之前 回复
xsxshxs2
xsxshxs2 回复wowo: 你好,还在吗
2 年多之前 回复
hfut_wowo
hfut_wowo 回复xsxshxs2: 这个算法是常量级的时间复杂度的,也就是遍历一下,OK的!
2 年多之前 回复
xsxshxs2
xsxshxs2 限时1秒唉
2 年多之前 回复
lxj9457
lxj9457 正解。
2 年多之前 回复
xsxshxs2
xsxshxs2   2015.07.07 19:45

有人吗……
感谢喽
在线等
立即采纳

xsxshxs2
xsxshxs2   2015.07.07 19:46

有人吗……
感谢喽
在线等
立即采纳

cj136071715
cj136071715   2015.07.07 21:08

public class N { public static int total(int[] a) { if (a == null || a.length == 0) { return 0; } int start = 1; int total = a[0]; while (true) { start = findLargest(start + 1, a); if (start >= a.length) { break; } total += a[start]; } return total; } public static int findLargest(int start, int[] a) { if (start >= a.length) { return start; } int max = a[start], position = start; for (int ix = start; ix < a.length; ix++) { if (a[ix] > max) { max = a[ix]; position = ix; } } return position; } public static void main(String[] args) { System.out.println(total(new int[]{5, 9, 4, 6, 10, 8, 7, 5, 4, 7})); }}

fengsigaoju
fengsigaoju   2015.07.07 22:23

#include
int main()
{

 int i,n,sum,j,temp;
 int a[1001];
 scanf("%d",&n);
 for (i=n-1;i>=0;i--)
    scanf("%d",&a[i]);
    sum=a[0]+a[n-1];
    i=1;
    temp=a[0];//开头和末尾一定是
    for (j=i;j<=n-2;j++)//比到之前一个因为第一个一定是
        if (a[j]>=temp)
        {
        sum=sum+a[j];//找到之前一个比它大的数
        temp=a[j];//更新最小值
        }

        printf("%d\n",sum);
    return 0;

}

xsxshxs2
xsxshxs2 200000的会爆
2 年多之前 回复
hfut_wowo
hfut_wowo   2015.07.08 20:02

<?php

$a = array(5, 9, 4, 6, 10, 8, 7, 5, 4, 7,);
$flag = $a[count($a)-1];
$sum = $a[0] + $a[count($a)-1];
for($i = count($a)-2; $i > 0; $i--){
if($a[$i] >= $flag){
$flag = $a[$i];
$sum += $a[$i];
}
}
echo $sum;exit;

Csdn user default icon
上传中...
上传图片
插入图片