首页 > ACM题库 > HDU-杭电 > HDU 4163-Stock Prices[解题报告]HOJ
2015
05-23

HDU 4163-Stock Prices[解题报告]HOJ

Stock Prices

问题描述 :

Buy low, sell high. That is what one should do to make profit in the stock market (we will ignore short selling here). Of course, no one can tell the price of a stock in the future, so it is difficult to know exactly when to buy and sell and how much profit one can make by repeatedly buying and selling a stock.

But if you do have the history of price of a stock for the last n days, it is certainly possible to determine the maximum profit that could have been made. Instead, we are interested in finding the k1 lowest prices and k2 highest prices in the history.

输入:

The input consists of a number of cases. The first line of each case starts with positive integers n, k1, and k2 on a line (n <= 1,000,000, k1 + k2 <= n, k1, k2 <= 100). The next line contains integers giving the prices of a stock in the last n days: the i-th integer (1 <= i <= n) gives the stock price on day i. The stock prices are non-negative. The input is terminated by n = k1 = k2 = 0, and that case should not be processed.

输出:

The input consists of a number of cases. The first line of each case starts with positive integers n, k1, and k2 on a line (n <= 1,000,000, k1 + k2 <= n, k1, k2 <= 100). The next line contains integers giving the prices of a stock in the last n days: the i-th integer (1 <= i <= n) gives the stock price on day i. The stock prices are non-negative. The input is terminated by n = k1 = k2 = 0, and that case should not be processed.

样例输入:

10 3 2
1 2 3 4 5 6 7 8 9 10
10 3 2
10 9 8 7 6 5 4 3 2 1
0 0 0

样例输出:

Case 1
1 2 3
10 9
Case 2
8 9 10
2 1

#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct
{
    int p,th;
}price;
price a[2000000];
bool cmp1(price a,price b)
{
    if(a.p<b.p) return true;
    if(a.p>b.p) return false;
    return a.th<b.th;
}
bool cmp11(price a,price b)
{
    return a.th<b.th;
}
bool cmp22(price a,price b)
{
    return a.th>b.th;
}
int main()
{
    int n,p,q,count(0);
    while(scanf("%d%d%d",&n,&p,&q)!=EOF&&n&&p&&q)
    {
        for(int i=0;i<n;i++)
            a[i].th=i+1,scanf("%d",&a[i].p);
        printf("Case %d\n",++count);
        sort(a,a+n,cmp1);
        sort(a,a+p,cmp11);
        sort(a+n-q,a+n,cmp22);
        for(int i=0;i<p;i++)
            if(p-1-i) printf("%d ",a[i].th);
                else printf("%d\n",a[i].th);
        for(int i=0;i<q;i++)
            if(q-1-i) printf("%d ",a[n-q+i].th);
            else printf("%d\n",a[n-q+i].th);
    }
    return 0;
}

  1. 薛蛮子幼年住在北京头发胡同,13岁时父亲薛子正因文化大革命被隔离审查,关入监狱。15岁时薛蛮子响应毛泽东的号召,前往内蒙古乌拉特前旗的一个村子做知青。在那里呆了两年,欠公社100多人民币,还曾摔断手臂。他之后逃回北京,依靠母亲的工资生活。1976年出狱的