纪念一下自己的第一篇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 = ; i < N; i++)

        cin >> StudentList[i];

    Node* nodelist = new Node[N];

    for (int i = ; i < N; i++)

    {

        nodelist[i].number = StudentList[i];

        nodelist[i].index = i;

    }

    cin >> Num >> Gap;

    Quicksort(nodelist, , N - );

    long long result = nodelist[N - ].number;

    int count = ;

    for (int i = N - ; i >=  && count <= Num; i--)

    {

        if (abs(nodelist[i].index - nodelist[i + ].index) <= Gap)

            result *= nodelist[i].number;

    }

    cout << result << endl;

    return ;

}

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

{

    if (left < right)

    {

        int base = divide(nodelist, left, right);

        Quicksort(nodelist, base + , right);

        Quicksort(nodelist, left, base - );

    }

}

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;

}