紀念一下自己的第一篇cnblog

2016-08-1016:33:22

// Netease.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include<iostream>
#include<cmath>

using namespace std;


struct Node
{
    int number;
    int index;
};

void Quicksort(Node* nodelist, int left, int right);
int divide(Node* nodelist, int left, int right);

int main()
{
    int N;
    int Num;
    int Gap;
    cin >> N;
    int* StudentList = new int[N];
    for (int i = 0; i < N; i++)
        cin >> StudentList[i];
    Node* nodelist = new Node[N];
    for (int i = 0; i < N; i++)
    {
        nodelist[i].number = StudentList[i];
        nodelist[i].index = i;
    }
    cin >> Num >> Gap;
    Quicksort(nodelist, 0, N - 1);
    long long result = nodelist[N - 1].number;
    int count = 1;
    for (int i = N - 2; i >= 0 && count <= Num; i--)
    {
        if (abs(nodelist[i].index - nodelist[i + 1].index) <= Gap)
            result *= nodelist[i].number;
    }
    cout << result << endl;
    return 0;
}


void Quicksort(Node* nodelist, int left, int right)
{
    if (left < right)
    {
        int base = divide(nodelist, left, right);
        Quicksort(nodelist, base + 1, right);
        Quicksort(nodelist, left, base - 1);
    }
}

int divide(Node* nodelist, int left, int right)
{
    Node temp = nodelist[left];
    int base = nodelist[left].number;
    while (left < right)
    {
        for (; right > left && nodelist[right].number > base; right--);
        nodelist[left] = nodelist[right];
        for (; right > left && nodelist[left].number < base; left++);
        nodelist[right] = nodelist[left];
    }
    nodelist[left] = temp;
    return left;
}