Question

c++拿糖果编程题目，请帮我讲解算法思想或者给出源代码，谢谢

HSP和他的女朋友ZM来到了商店，商店有n个糖果，标号依次为1,2,3....n，对应的价值为W1,W2,W3...Wn。现在HSP先拿走一个标号为a的糖果，标号小于a的糖果就被ZM收回去了，然后HSP只能在剩下的糖果中选一个标号为b的糖果，请问Wa-Wb的最大值是多少？

Answer 1

因为HSP拿走a糖果，小于a的被ZM拿走，b糖果只能在大于a的糖果内选择。
对于给定一个a，b选择为大于a的糖果中Wb最小的那个，Wa-Wb的就会取到最大值。
1.我们让a=1，b=大于1的糖果中取Wb最小值的那个，得到Wa-Wb。
2.我们让a=2，b=大于2的糖果中取Wb最小值的那个，得到Wa-Wb。
...
然后在这n种Wa-Wb中找到最大值即为所有情况的最大值。

int max=0;
for(int a=1;a<=n-1;++a){
    for(int b=a+1;b<=n;++b){
        找到最小的W[b]的下标;
    }
    int newMax=W[a]-W[b];
    if(newMax>max)max=newMax;
}
//代码时间复杂度为O(n^2)，空间复杂度为O(1)。

如果让a从n-1到1，反过来，就可以不用每次都从头寻找最小值的Wb。

int Wb=W[n];
int max=0;
for(int a=n-1;a<=1;--a){
    int newMax=W[a]-Wb;
    if(newMax>max)max=newMax;
    if(W[a]<Wb)Wb=W[a];
}
//代码时间复杂度为O(n)，空间复杂度为O(1)。

追问

感谢你的回答，解决了我的问题。但是我还有一点请教，就是针对我这个题目，怎么样写代码输入呢。首先，我这样
cin>>N;
for(int i=0;i<N;i++)
{
......
}
中间省略号的部分，我怎么写代码。可以实现不同数目的数组的输入呢？他前面也不让输入一个n，让我用for循环输入n个输，他让直接输入，我怎么样可以输不同个数目呢？

Answer 2

#include <iostream>
#define Max 100000
using namespace std;

void rank_bub(int array[ ],int n){
    int temp;   
    for(int i=0;i<n-1;i++)    
        for(int j=0;j<n-i-1;j++)            
            if(array[j+1]<array[j]){                
                temp=array[j+1];               
                array[j+1]=array[j];                
                array[j]=temp;
            }
}
int main(int argc, char *argv[])
{
    int n,m,i,j;
    int array[Max];
    cin>>n;
    int out[n];
    m=0;
    for(i=0;i<n;i++){
        j=0;
        do cin>>array[j++]; 
        while(cin.get()!='\n'); 
        if(j>1){     
        rank_bub(array,j);
        out[m++]=array[j-1]-array[0];
        }
    } 
    for(i=0;i<m;cout<<out[i++]<<endl);
    return 0;
}

追问

谢谢你的回答，解决了我输入的问题。但是我想您理解错了题意，您求得结果是一个数组的最大值和最小值的差值。但题目有要求，是大数在左，小数在右，求差值。不过还是感谢您解决了我输入的问题。