2017年，完美世界c/c++ 夏季实习面试题
只有俩道编程题，但是我都没有accept，贴出我的答案
和交卷之后自己想的答案，希望得到一个不一样的想法。

1. 小明要持续打卡，但是呢上班又很没有意思，所以给自己找了一件事情做

那就是学习做菜，第i道，需要a[i]个单位的肉。但是肉是一整块的，每次切都
需要消耗小明的活力，消耗活力等于肉的大小（单位）。小明的刀法很好每
一次都可以切下来需要的肉。请问做n道菜，小明最少需要多少活力。

输入

3 / 总共有多少道菜 /
8 / 第一道菜 需要8单位的肉 /
5
8

输出

34

我的解答 通过率10% 使用c语言

我的想法是，每次需要消耗的活力是肉的单位大小，那每次切去最大单位的肉

消耗的活力肯定是最小的吧，所以排序之后，肉的总单位从后往前减去排序后的每道
菜需要的肉。这样得到的肯定是最小活力，但是就是不对，现在还没有想明白呢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>  
#include <string.h>  
void Bublesort(int a[],int n)
{
    int i,j,k;
    for(j=0;j<n-1;j++)  
    {
        for(i=0;i<n-j-1;i++)  
        {
            if(a[i]>a[i+1])  
            {
                k=a[i];
                a[i]=a[i+1];
                a[i+1]=k;
            }
        }
    }
}
int main()  
{  
    int n;
    scanf("%d", &n);
    int array[n];
    int index = 0;
    int result = 0;
    while(index < n)
    {
        scanf("%d", &array[index++]);
        result += array[index-1];
    }
    Bublesort(array, n);
    n = 0;
    while(--index > 0)
    { 
        n = n + result ;
        result -= array[index];
    }
    printf("%d\n", n); 
}

2. 小明一不小心回到了2015年，而且记得未来n天的股票走势图，但是

害怕股票监管局的调查，只能有一个买入和卖出的机会，选出小明哪天
买入 ，哪天卖出可以得到最大收益。（相同的收益，最晚买入和最早卖出
是最佳收益，如果没有收益输出-1，-1.），天数从0开始。

输入

3 / 知道的未来n天股票走势 /
1 / 第0天股票价格 /
5 / 第1天股票价格 /
3 / 第2天股票价格 /

输出

0,1

我的代码(提交的代码）通过率87%

想法

把股票按生序排序，，然后排除股票价格一样的情况

然后把最小值和原数组进行对比，找到最晚的最小值，如果有
相同的最小值的话。把最大值和原数组进行对比，找到第一个。
这样就满足了最晚买入和最早卖出的原则。但是没有考虑到如果
5 1 3 ，1 3 5 ；这种情况，假如第一天就是最高价格，这样我
的就直接输出-1，,1其实，1 3 才是最佳收益啊，我就是忽略了
这种情况。我自己觉得，所以才有了下面的代码2。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>  
#include <string.h>  
        void Bublesort(int a[],int n)
        {
        int i,j,k;
        for(j=0;j<n-1;j++)  
        {
        for(i=0;i<n-j-1;i++)  
        {
        if(a[i]>a[i+1])  
        {
        k=a[i];
        a[i]=a[i+1];
        a[i+1]=k;
        }
        }
        }
        }
        void maxBT(int[] a, int []b, int length,int l, int r)
        {
            for(index = 0; index < n; index++)  
                if (array_cp[0] == array_a[index])
                    buy = index;
            for(index = 0; index < n; index++) 
                if (array_cp[n-1] == array_a[index]) {
                    out = index;
                    break;
                }
            if( buy > out  ) { 
                printf("%d,%d\n", -1, -1); 
                return;
            }    
        }
void main()  
{  
    int n;
    scanf("%d", &n);
    int array_a[n];
    int array_cp[n];
    int index = 0;
    int buy = -1;
    int out = -1;
    while(index < n) {
        scanf("%d", array_cp+index);
        array_a[index] =  array_cp[index];
        index++;
    }   
    Bublesort(array_cp, n);
    if(array_cp[n-1] == array_cp[0]) { 
        printf("%d,%d\n", buy, out); 
        return;
    }    
    printf("%d,%d\n", buy, out); 
    return ;

我的代码(交卷又想了想重新写的)

想法

因为存在，股票最大值 和最小值 在最前面或者最后这种情况，所以需要

处理这种情况，知道找到最佳收益，这样的话就需要递归处理了，毕竟不知道
这种情况会出现多少次。刚好听了别人对这道题的解法所以就写了出来。
就是暴力求解法，把第一天和后面的每一天都比较找到最大的收益然后
接着把第二天和后面的每一天都进行比较找最大收益。这样就不存在递归情况
而且时间复杂度也就是冒泡排序的复杂度O(n^2). 最后需要考虑一下，最小间隔
就是最佳收益，如果存在相同的时间间隔，那就取栈的前面就可以了。相同时间
间隔，越早得到最大收益，风险越小，属于最佳收益。我们是这样想法，至于对不对
就不知道了。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>  
#include <string.h>  
int stack[10];
int top = -1;
void push(int a)
{
    stack[++top] = a;
}
int pop()
{
    return stack[top--];
}
void Bublesort(int a[], int n)
{
    int i,j,k;
    int max = 0;
    int m = 1;
    for(j=0;j<n-1;j++)  
    {
        for(i=j+1;i<n;i++)  
        {   
            m = a[i] - a[j];
            if (max == m) {
                push(j);
                push(i);
            }
            if (max < m) {
                top = -1;
                max = m;
                push(j);
                push(i);
            }
        }
    }
}
void main()  
{  
    int n;
    scanf("%d", &n);
    int array_a[n];
    int array_cp[n];
    int index = 0;
    int buy = -1;
    int out = -1;
    while(index < n) {
        scanf("%d", array_cp+index++);
    }   
    Bublesort(array_cp, n);
    if (top == -1) /* stack is empty */
    {
        printf("%d,%d\n", buy, out); 
        return;
    }
    /* for(index=0; index<=top; index++)
       printf("%d  ", stack[index]); 
       printf("\n");
     */
    int count = 0;
    int min_length = 655;
    int length;
    int result = -1;
    for (index = top; index >0; index-=2) {
        length =  stack[index] - stack[index-1];
        if (min_length == length) {
            count++;
            result = index;
        }
        if (min_length > length) {
            min_length = length;
            count = 0;
            result = index;
        }
    }
    printf("%d,%d\n", stack[result-1], stack[result]); 
    return ;
}