首页 > 试题广场 >

对于非负序列a1、a2、……、an,在数轴上做垂线连接点(i

[问答题]
对于非负序列a1、a2、……、an,在数轴上做垂线连接点(i,0)和(i,ai)。选择这样的两条线和x轴可以形成一个容器,我们以面积代表所装的水,求以这种方式构成的容器能装的最大面积。比如选择a2=3、a5=6,则所装的面积为9.
int maxArea(vector<int>& height) {
    int water = 0;
    int i = 0, j = height.size() - 1;
    while (i < j) {
        int h = min(height[i], height[j]);
        water = max(water, (j - i) * h);
        while (height[i] <= h && i < j) i++;
        while (height[j] <= h && i < j) j--;
    }
    return water;
}
发表于 2015-08-29 10:18:02 回复(0)
这是最大装水问题,其解决过程为

编辑于 2015-12-15 10:24:16 回复(0)
两端逼近法
发表于 2016-08-07 23:24:28 回复(0)


import java.util.*;
public class Main{
    public static void main(String[] args){
    int[] a = new int[100000];
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    for(int i =0;i <n;i++){
    System.out.println(a[i]);
    }
    int sum = 0;
    for(int i = 0;i < n;i++){
    for(int j = i+1;j < n;j++){
    if((j - i)*min(a[i],a[j])>sum){
    sum = (j - i)*min(a[i],a[j]);
    }
    }
    }
    System.out.println(sum);
    }

private static int min(int i, int j) {
// TODO Auto-generated method stub
return i<j?i:j;
}
}
发表于 2016-04-09 15:08:55 回复(0)
我怎么没看懂这题目什么意思呢?谁能解释一下
发表于 2015-08-25 10:44:20 回复(2)
<pre class="prettyprint lang-cpp">#include&lt;iostream&gt; #include&lt;cmath&gt; using namespace std; const int N = n+1; int series[N]={}; int main(){ int first,second; int square; cin &gt;&gt; first &gt;&gt; second; if(series[first]&gt;series[second]) &nbsp; square = series[second]*abs(second-first); else square = series[first]*abs(second-first); cout &lt;&lt; square &lt;&lt; endl; return 0; }</pre> <br />
发表于 2015-08-22 15:02:41 回复(0)
#include <stdio.h>

void MaxValue( int ai[], int n, int *value)

{

    if (n <= 0 ) return ;

    

    int i, j, k = 0 , temp = 0 ;

    int number = ( int )n*(n- 1 )* 0.5 ;

    int aNew[number];

    

    // 求出所有的结果存放到 aNew[] 数组中

    for (i = 0 ; i < n - 1 ; i++)

    {

        for (j = i + 1 ; j < n; j++)

        {

            if (ai[i] > ai[j])

            {

                aNew[k] = (j - i)*ai[j];

            } else {

                aNew[k] = (j - i)*ai[i];

            }

            k++;

        }

    }

    

    // 用冒泡法把得到的所有结果排序

    for (i = 0 ; i < number - 1 ; i++)

    {

        for (j = i + 1 ; j < number; j++)

        {

            if (aNew[i] > aNew[j])

            {

                temp = aNew[i];

                aNew[i] = aNew[j];

                aNew[j] = temp;

            }

        }

    }

    *value = aNew[number- 1 ];

}

int main ()

{

    int a[ 4 ] = { 4 , 10 , 9 , 5 };

    int myValue;

    MaxValue(a, 4 , &myValue);

    printf( "%d" , myValue);

    return 0 ;

}


/*

  测试的输出结果为:

 

 i = 0, j = 1, j - i = 1, ai[i] = 4,  ai[j] = 10, aNew[0] = 4

 i = 0, j = 2, j - i = 2, ai[i] = 4,  ai[j] = 9,  aNew[1] = 8

 i = 0, j = 3, j - i = 3, ai[i] = 4,  ai[j] = 5,  aNew[2] = 12

 i = 1, j = 2, j - i = 1, ai[i] = 10, ai[j] = 9,  aNew[3] = 9

 i = 1, j = 3, j - i = 2, ai[i] = 10, ai[j] = 5,  aNew[4] = 10

 i = 2, j = 3, j - i = 1, ai[i] = 9,  ai[j] = 5,  aNew[5] = 5

  排序后的数组为:

 aNew[6] = {4, 5, 8, 9, 10, 12};

  最后所要求的值为:

 12

 */  

编辑于 2015-08-21 22:13:35 回复(0)
题目意思:比如A2=3,A5=6,可以画出如下坐标系
package conmon.niuke;
public class VatProblem {
	
	public static void main(String[] args){
		int[][] a={{2,5,7},          //key集合
				   {3,6,5}};         //value集合
		System.out.println(getMaxVat(a));
	}
	
	
	/**求出最大的桶
	 * @param a
	 * @return
	 */
	public static int getMaxVat(int[][] a){
		int max=count(a[0][0],a[1][0],a[0][1],a[1][1]);       //循环求出最大的桶
		for(int i=1;i<a[0].length-1;i++){
			int temp=count(a[0][i],a[1][i],a[0][i+1],a[1][i+1]);
			max=max>temp?max:temp;
		}
		return max;
	}
	
	/**计算桶面积
	 * @param i
	 * @param ai
	 * @param j
	 * @param aj
	 * @return
	 */
	public static int count(int i,int ai,int j,int aj){
		int height=ai,width=Math.abs(j-i);
		if(ai>aj){
			height=aj;
		}
		return height*width;
	}

}

编辑于 2015-09-01 18:54:54 回复(0)
#include <iostream>
using namespace std;

int maxArea(int a[], int size){
    int i,j,lastj=size-1;
    int maxarea=0;
    for(i=0;i<size;++i){
        for(j=size-1;j>i;--j){
            if(lastj-a[i]>a[j]-a[i])   continue;
            int t_area=(j-i)*(a[j]-a[i]);
            if(t_area<0)	t_area=-t_area;
            if(t_area>maxarea)    maxarea = t_area;
        }
   }
    return maxarea;
}

int main(){
    int a[]={1,2,3,4,5,6,7};
    cout<<maxArea(a, sizeof(a)/sizeof(a[0]));
    return 0;
}

发表于 2015-08-03 19:45:42 回复(0)


发表于 2015-07-30 22:01:17 回复(0)
class Program
    {
        static void Main(string[] args)
        {
            int n;
            int [] A=new int[]{};
            int s = 0;
            for (int i = 0; i < n; i++)
            {
                s = A[0] + A[n];

            }
            Console.WriteLine(s);
            Console.ReadKey();

        }

发表于 2015-07-13 23:22:18 回复(0)
容器盛水问题   找最小的边                  题目提交了有没有oj之类的判题???????
发表于 2015-07-09 10:20:11 回复(0)
代码如下:

int maxArea(int height[], int n) {
    int head = 0, tail = n - 1;
	int max = 0, temp = 0;
	while (head < tail) {
	temp = tail - head;
	if (height[head] < height[tail]) {
		temp *= height[head];
		head++;
	}
	else {
		temp *= height[tail];
		tail--;
	}
	if (temp > max) {
		max = temp;
		}
	}
	return max;
}
编辑于 2015-07-08 16:41:43 回复(2)