知識點：堆

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

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

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

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

本題還有更簡單的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海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

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

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

廣告

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