zerojudge c364. 我鄙視你

題目在 https://zerojudge.tw/ShowProblem?problemid=c364

這題最多有100萬筆的輸入加上100萬筆的輸出並且要在1秒內完成, 輸出入用scanf和printf比較快.

用cin和cout也可以過. 但是演算法要夠快呀.

解題思路是由於排成一列的人身高像是山坡有上下起伏. 每個人鄙視的其他人身高來自左右兩邊. 那先計算完每個鄙視左邊人的身高, 鄙視右邊的人的身高用同樣的演算法再算一遍就好了.

那左邊怎麼算呢?假設輸入的身高代表人由左排到右邊, 身高會變低,不變或變高. 變低或不變這種情形都不會被右邊的人鄙視, 只會被未知的以後更高的人鄙視. 所以就先不用計算, 把它推入堆疊中等待.

unsigned long long VLeft=Height[0]; //左邊的人
	for(i=1;i<N;i++){
		unsigned long long VRight=Height[i]; //右邊的人
		if(VLeft>=VRight){
			mystack[stackptr++]=i-1;  //左邊的人推入堆疊
			VLeft=VRight;
			continue;
		}
                ...

C++

那如果變高了表示左邊的人會被右邊的人鄙視, 就把左邊的身高和它鄙視的身高都加給右邊的人,然後再去檢查堆疊裡的人的身高是不是也低於右邊的人, 如果是就把它POP出來, 把他的身高和他鄙視的身高也加給右邊的人,

//v左邊的身高和它鄙視的身高都加給右邊的人
                LeftAll[i]+=(VLeft+LeftAll[i-1]); 

		while(stackptr>0){//檢查堆疊裡的人的身高是不是也低於右邊的人
			int top = mystack[stackptr-1];
			if(Height[top]<VRight){
                                //把他的身高和他鄙視的身高也加給右邊的人
				LeftAll[i]+=(Height[top]+LeftAll[top]);
				stackptr--;//把它POP出來
				continue;
			}
			break;
		}

C++

從左到右輸入完, 左邊的鄙視身高就全部算完了. 再反過來算完鄙視右邊的身高, 兩邊加起來就是答案了.

for(i=0;i<N;i++){
	printf("%lld\n", LeftAll[i]+RightAll[i]);
	}

C++

完整程式碼如下:

#include <stdio.h>

using namespace std;

unsigned long long Height[1000000];  //每個人的身高
unsigned long long LeftAll[1000000]; //儲存每個人鄙視左邊的人的身高
unsigned long long RightAll[1000000];//儲存每個人鄙視右邊的人的身高

unsigned long long mystack[1000000]; //簡單的堆疊
int stackptr; //堆疊指標

int main(){

	int N;
	scanf("%d", &N);

	int i=0;
	while (i<N){
		scanf("%lld",&Height[i++]);
	}

        //鄙視左邊的人的身高
	stackptr=0;

	unsigned long long VLeft=Height[0];
	for(i=1;i<N;i++){
		unsigned long long VRight=Height[i];
		if(VLeft>=VRight){
			mystack[stackptr++]=i-1;
			VLeft=VRight;
			continue;
		}

		LeftAll[i]+=(VLeft+LeftAll[i-1]);

		while(stackptr>0){
			int top = mystack[stackptr-1];
			if(Height[top]<VRight){
				LeftAll[i]+=(Height[top]+LeftAll[top]);
				stackptr--;
				continue;
			}
			break;
		}
		VLeft = VRight;
	}


        //鄙視右邊的人的身高
	stackptr=0;

	unsigned long long VRight=Height[N-1];
	for(i=N-2;i>=0;i--){
		unsigned long long VLeft=Height[i];

		if(VLeft<=VRight){
			mystack[stackptr++]=i+1;
			VRight=VLeft;
			continue;
		}

		RightAll[i]+=(VRight+RightAll[i+1]);

		while(stackptr>0){
			int top = mystack[stackptr-1];
			if(Height[top]<VLeft){
				RightAll[i]+=(Height[top]+RightAll[top]);
				stackptr--;
				continue;
			}
			break;
		}
		VRight=VLeft;
	}

        //輸出答案
	for(i=0;i<N;i++){
		printf("%lld\n", LeftAll[i]+RightAll[i]);
	}
}

C++

zerojudge c364. 我鄙視你

Archives

Categories