[NPSC] 2009初賽 E. 檸檬汽水傳說

題目連結:http://contest.cc.ntu.edu.tw/npsc2009/2009sen.pdf
不 本題複雜度大概要做到$O(n)$或$O(n \log n)$,所以明顯naive的枚舉點對做法是不可能會好的,不妨思考其實每個人都只要往一邊看就好了,而且當看到一個比自己大的數就可以停了,那應該可用stack做,而明顯要用stack做的話,要有一定的單調性,想想後發現遞減的是好的,每次都pop掉比自己小的人並把pop了幾個加上去,不過值得注意的是如果是pop掉跟自己一樣的人的話,記得要把他原本的size記錄下來,之後要擺回去,因為其他人都還是可以跟你做匹配之類的,此外因為每個人都還可以跟隔壁的人溝通,所以當隔壁有人時記得多加一。
#include <bits/stdc++.h>
using namespace std;

class knight{
	private:
		int __val;
		long long __size;
	public:
		knight(int a,int b){__val=a;__size=b;}
		int operator++(int a){if(a==0)return __size++;}
		bool operator<=(int a){return __val<=a;}
		bool operator==(int a){return __val==a;}
		friend void operator+=(long long &a, knight b){a+=b.__size;}
};

stack<knight> ss;

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int sz;
		long long ans=0;
		scanf("%d",&sz);
		while(!ss.empty())ss.pop();
		for(int i=0;i<sz;i++){
			int aaa;
			scanf("%d",&aaa);
			long long kk=1;
			while(!ss.empty()&&(ss.top()<=aaa)){
				if(ss.top()==aaa) kk+=ss.top();
				ans+=ss.top();
				ss.pop();
			}
			if(!ss.empty())ans++;
			ss.push(knight(aaa,kk));
		}
		printf("%lld\n",ans);
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology