Stock Prices
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 987 Accepted Submission(s): 397
Problem Description
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.
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.
Input
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.
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.
Output
For
each case, produce three lines of output. The first line contains the
case number (starting from 1) on one line. The second line specifies the
days on which the k1 lowest stock prices occur. The days are sorted in
ascending order. The third line specifies the days on which the k2
highest stock prices occur, and the days sorted in descending order. The
entries in each list should be separated by a single space. If there
are multiple correct lists for the lowest prices, choose the
lexicographically smallest list. If there are multiple correct lists for
the highest prices, choose the lexicographically largest list.
each case, produce three lines of output. The first line contains the
case number (starting from 1) on one line. The second line specifies the
days on which the k1 lowest stock prices occur. The days are sorted in
ascending order. The third line specifies the days on which the k2
highest stock prices occur, and the days sorted in descending order. The
entries in each list should be separated by a single space. If there
are multiple correct lists for the lowest prices, choose the
lexicographically smallest list. If there are multiple correct lists for
the highest prices, choose the lexicographically largest list.
Sample Input
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
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
Sample Output
Case 1
1 2 3
10 9
Case 2
8 9 10
2 1
1 2 3
10 9
Case 2
8 9 10
2 1
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 1000001
const int inf=0x7fffffff; //无限大
struct node
{
int x;
int y;
};
node a[maxn];
node b[maxn];
bool cmp(node c,node d)
{
if(c.x==d.x)
return c.y<d.y;
return c.x<d.x;
}
bool cmp1(node c,node d)
{
return c.y>d.y;
}
bool cmp2(node c,node d)
{
return c.y<d.y;
}
int main()
{
int n,k1,k2;
int cas=;
while(scanf("%d%d%d",&n,&k1,&k2)!=EOF)
{
if(n==)
break;
for(int i=;i<n;i++)
{
scanf("%d",&a[i].x);
a[i].y=i+;
}
sort(a,a+n,cmp);
sort(a,a+k1,cmp2);
sort(a+n-k2,a+n,cmp1);
printf("Case %d\n",cas++);
int first=;
for(int i=;i<k1;i++)
{
if(first)
{
printf("%d",a[i].y);
first=;
}
else
printf(" %d",a[i].y);
}
printf("\n");
first=;
for(int i=n-k2;i<n;i++)
{
if(first)
{
printf("%d",a[i].y);
first=;
}
else
printf(" %d",a[i].y);
}
printf("\n");
}
return ;
}