首页 > 代码库 > hdu 4163 Stock Prices 花式排序
hdu 4163 Stock Prices 花式排序
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.
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.
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.
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.
Sample Input
10 3 21 2 3 4 5 6 7 8 9 1010 3 210 9 8 7 6 5 4 3 2 10 0 0
Sample Output
Case 11 2 310 9Case 28 9 102 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 1000001const 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=1; while(scanf("%d%d%d",&n,&k1,&k2)!=EOF) { if(n==0) break; for(int i=0;i<n;i++) { scanf("%d",&a[i].x); a[i].y=i+1; } sort(a,a+n,cmp); sort(a,a+k1,cmp2); sort(a+n-k2,a+n,cmp1); printf("Case %d\n",cas++); int first=1; for(int i=0;i<k1;i++) { if(first) { printf("%d",a[i].y); first=0; } else printf(" %d",a[i].y); } printf("\n"); first=1; for(int i=n-k2;i<n;i++) { if(first) { printf("%d",a[i].y); first=0; } else printf(" %d",a[i].y); } printf("\n"); } return 0;}
hdu 4163 Stock Prices 花式排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。