知識(shí)點(diǎn)：堆

專業(yè)從事企業(yè)網(wǎng)站建設(shè)和網(wǎng)站設(shè)計(jì)服務(wù)，包括網(wǎng)站建設(shè)、域名注冊(cè)、雅安服務(wù)器托管、企業(yè)郵箱、微信公眾號(hào)開發(fā)、微信支付寶成都小程序開發(fā)、成都App制作、軟件開發(fā)、等服務(wù)。公司始終通過(guò)不懈的努力和以更高的目標(biāo)來(lái)要求自己,在不斷完善自身管理模式和提高技術(shù)研發(fā)能力的同時(shí)，大力倡導(dǎo)推行新經(jīng)濟(jì)品牌戰(zhàn)略，促進(jìn)互聯(lián)網(wǎng)事業(yè)的發(fā)展。

這個(gè)題的題意比較好理解，但是比較容易寫錯(cuò)，至少我是這么感覺(jué)的，看到題，可以很自然的想到用兩個(gè)堆，一個(gè)大根堆一個(gè)小根堆來(lái)維護(hù)數(shù)據(jù)，但是這個(gè)不是對(duì)頂堆，然后每一天的最后，我們從分別拿出來(lái)一個(gè)數(shù)，統(tǒng)計(jì)答案就行了，題目保證每天的最后都至少有兩張，這個(gè)想法很自然，但是這個(gè)樣子是可能出錯(cuò)的，想象一下，假如實(shí)際剩余的消費(fèi)券已經(jīng)不多了，但是你用完的消費(fèi)券已經(jīng)很多了，然后來(lái)了一張很小的消費(fèi)券，那么它進(jìn)入大根堆的話就會(huì)被放的很靠后，前面有很多實(shí)際已經(jīng)用完的但是還沒(méi)有被你出堆的消費(fèi)券，然后那些消費(fèi)券都像是被向前推了一下似的，就有可能會(huì)有一個(gè)實(shí)際已經(jīng)被用過(guò)的再被使用，這樣就錯(cuò)了，出錯(cuò)的地方就在于有些用完的消費(fèi)券不能留著了，又看了看數(shù)據(jù)，每個(gè)消費(fèi)券的數(shù)據(jù)范圍正好可以來(lái)散列，那么就是這個(gè)樣子了，我們開一數(shù)組來(lái)散列記錄每種消費(fèi)券的數(shù)目，每天結(jié)束的時(shí)候，循環(huán)遍歷，數(shù)目為零的券都直接刪除，直到找到第一個(gè)數(shù)目不為零的券，用來(lái)統(tǒng)計(jì)答案，兩個(gè)堆都是這個(gè)樣子，這樣就不會(huì)出錯(cuò)了，

這個(gè)題用堆寫容易出錯(cuò)的地方就是沒(méi)有及時(shí)刪除堆里面實(shí)際數(shù)量已經(jīng)是0的消費(fèi)券，所以每次從堆里面找消費(fèi)券的時(shí)候都要找第一個(gè)數(shù)量不為0的消費(fèi)券，并且前面的都要?jiǎng)h除

還是感慨一下，一開始看見這個(gè)題就有點(diǎn)輕敵了，以為很簡(jiǎn)單，最后是看了別人的題解才過(guò)的，希望自己以后不要這么輕敵了

本題還有更簡(jiǎn)單的multiset的寫法，就不寫了

#includeusing namespace std;

const int N = 1e6 + 5;

int h[N];

int main() {
	int n;
	while (cin >>n && n) {
		memset(h, 0, sizeof(h));
		priority_queueq1;
		priority_queue, greater>q2;
		long long ans = 0;
		while (n--) {
			int k;
			scanf("%d", &k);
			while (k--) {
				int x;
				scanf("%d", &x);
				q1.push(x); q2.push(x);
				h[x]++;
			}
			while (!h[q1.top()]) q1.pop();
			while (!h[q2.top()]) q2.pop();
			ans += (long long) q1.top() - q2.top();
			h[q1.top()]--; h[q2.top()]--;
		}
		cout<< ans<< '\n';
	}
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：UVA11136Hoaxorwhat-創(chuàng)新互聯(lián)
新聞來(lái)源：http://chinadenli.net/article18/dgppgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、品牌網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、網(wǎng)頁(yè)設(shè)計(jì)公司、企業(yè)建站、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)