首页 > ACM题库 > HDU-杭电 > hdu 2385 Stock-并查集-[解题报告]C++
2014
01-05

hdu 2385 Stock-并查集-[解题报告]C++

Stock

问题描述 :

Optiver sponsored problem.

After years of hard work Optiver has developed a mathematical model that allows them to predict wether or not a company will be succesful. This obviously gives them a great advantage on the stock market.

In the past, Optiver made a deal with a big company, which forces them to buy shares of the company according to a fixed schedule. Unfortunately, Optiver’s model has determined that the company will go bankrupt after exactly n days, after which their shares will become worthless.

Still, Optiver holds a large number of sell options that allows them to sell some of the shares before the company goes bankrupt. However, there is a limit on the number of shares Optiver can sell every day, and price Optiver receives for a share may vary from day to day. Therefore, it is not immediately clear when Optiver should sell their shares to maximize their profit, so they asked you to write a program to calculcate this.

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (1 <= n <= 100 000): the number of days before the company goes bankrupt.

n lines with three integers xi (0 <= xi <= 100), pi (0 <= pi <= 100) and mi (0 <= mi <= 10 000 000): the number of shares Optiver receives on day i, the (selling) price per share on day i, and the maximum number of shares Optiver can sell on day i, respectively.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (1 <= n <= 100 000): the number of days before the company goes bankrupt.

n lines with three integers xi (0 <= xi <= 100), pi (0 <= pi <= 100) and mi (0 <= mi <= 10 000 000): the number of shares Optiver receives on day i, the (selling) price per share on day i, and the maximum number of shares Optiver can sell on day i, respectively.

样例输入:

1
6
4 4 2
2 9 3
2 6 3
2 5 9
2 2 2
2 3 3

样例输出:

76

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int N = 30005;
int set[N];
int high[N]; //i元素上面(加上i)的元素个数 
int low[N];  //i元素下面的元素个数 
int findset(int x){
	if(x == set[x])
		return set[x];
	int tm = set[x];
	set[x] = findset(set[x]);
	low[x] += low[tm];
	return set[x];
}
void unionset(int x,int y){
	int fx = findset(x);
	int fy = findset(y);
	if( fx == fy)
		return ;
	set[fx] = fy;
	low[fx] += high[fy];
	high[fy] += high[fx];
}
int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		for(int i = 1; i <= N; i++){
			set[i] = i;
		         high[i] = 1;
		}
		memset(low,0,sizeof(low));
		char op;
		int x,y;
		getchar();
		for(int i =1 ; i <= n; i++){
			scanf("%c",&op);
			if(op == 'C'){
				scanf("%d",&x);
				findset(x);
				printf("%d\n",low[x]);
			}
			else{
				scanf("%d%d",&x,&y);
				unionset(x,y);
			}
			getchar();
		}
	}
	return 0;
}

解题转自:http://blog.csdn.net/fengshiye948/article/details/8779618


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的