日誌統計 - tw511教學網

 標題：日誌統計

小明維護着一個程式設計師論壇。現在他收集了一份"點贊"日誌，日誌共有N行。其中每一行的格式是：

ts id  

表示在ts時刻編號id的貼文收到一個"贊"。  

現在小明想統計有哪些貼文曾經是"熱帖"。如果一個貼文曾在任意一個長度爲D的時間段內收到不少於K個贊，小明就認爲這個貼文曾是"熱帖"。  

具體來說，如果存在某個時刻T滿足該帖在[T, T+D)這段時間內(注意是左閉右開區間)收到不少於K個贊，該帖就曾是"熱帖"。  

給定日誌，請你幫助小明統計出所有曾是"熱帖"的貼文編號。  

【輸入格式】
第一行包含三個整數N、D和K。  
以下N行每行一條日誌，包含兩個整數ts和id。  

對於50%的數據，1 <= K <= N <= 1000  
對於100%的數據，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000  

【輸出格式】
按從小到大的順序輸出熱帖id。每個id一行。  

【輸入樣例】
7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3  

【輸出樣例】
1  
3  


資源約定：
峯值記憶體消耗（含虛擬機器） < 256M
CPU消耗  < 1000ms


請嚴格按要求輸出，不要畫蛇添足地列印類似：「請您輸入...」 的多餘內容。

注意：
main函數需要返回0;
只使用ANSI C/ANSI C++ 標準;
不要呼叫依賴於編譯環境或操作系統的特殊函數。
所有依賴的函數必須明確地在原始檔中 #include <xxx>
不能通過工程設定而省略常用標頭檔案。

提交程式時，注意選擇所期望的語言型別和編譯器型別。

相信很多人一看到[T,T+D）的時候就已經想到這是在考察區間問題。

步驟：

按時間排序
從0-n分別做區間開頭找滿足條件的td

注意事項：假設不同起點爲區間,我命名爲[A,…)、[A+1,…)、[A+2,…)區間

[A,…)區間中計算結果都滿足於[A+1,…)區間，除了[A,…)的起點對應的td.
j從0-n不用回溯。

下面下麪演算法設計的妙處：

每一次開始新區間的時候j不用回溯，只需把前一個區間起點對應的td出現個數-1就行。
每一個td的數量不會無限增大，因爲在開始新區間時候都會把前一個區間起點對應的td出現個數-1；可能td=2這個值在2段不相連的區間都滿足：td出現個數>=k,把它加入set去重和排序就好了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
//日誌物件
struct R{
	int ts,td;
};
//自定義比較器
bool cmp(R r1,R r2){
	return r1.ts < r2.ts;	//從小到大排序
}

int main(){
	int n,d,k;				//輸入
	cin >> n >> d >> k;
	vector<R> records(n);	//記錄日記
	map<int,int> cnt;		//用來記錄在[Ti,Ti+j)時間內每一個dt出現的次數
	for(int i = 0;i < n;i++){
		cin >> records[i].ts >> records[i].td;	//輸入日誌
	}
	set<int> ans;			//記錄滿足條件的結果 
	//排序，自定義比較器
	sort(records.begin(),records.end(),cmp); 
	//尺取法-哨兵，不斷往後移動
	int j = 0;
	for(int i = 0;i < n;i++){
		while(j < n && records[j].ts - records[i].ts < d){//j時刻-i時刻 < d
			cnt[records[j].td]++;			//該id的值加1 
			if(cnt[records[j].td] >= k){	//如果計數滿足條件 
				ans.insert(records[j].td);	//將id放入ans中 
			}
			++j;							//往後移動
		}	
		cnt[records[i].td]--;				//重新設定新起點之前，必須將前一個起點的td移除——cnt[records[i].td]--.看下面 下麪的例1
	} 
	set<int>::iterator i = ans.begin();
	for(;i != ans.end();i++){
		cout << *i << endl;
	}
	return 0;
}

例1：
舊區間：[A,Aj)
在該區間內計算每一個td的數量並判斷：cnt[records[j].td] >= k
新區間：[A+1,Aj)
我們以A+1爲起點後就必須：cnt[records[i].td]–;因爲上一個區間records[A].td這個值不能把它算進去。