第10回ブルーブリッジカップA組C++試験問題G:出前店優先度

出前店優先度試験問題G:出前店優先度時間制限:1.0 sメモリ制限:512.0 MB本題総得点:20分【問題説明】「満腹か」出前システムではN軒の出前店を維持し、番号1〜N.各出前店には優先度があり、初期時(0時刻)の優先度は0です.1時間単位が経過するごとに、出前店に注文がなければ、優先度は1減少し、最低は0に減少します.出前店に注文がある場合は、優先度はマイナスではなく、1つの優先度に2を加えます.ある外食店のある時点の優先度が5より大きい場合、システムは優先キャッシュに追加されます.優先度が3以下の場合、優先キャッシュは消去されます.T時刻以内のM件の注文情報を指定し、T時刻にどのくらいの出前店が優先キャッシュにあるかを計算してください.第1行目は、3つの整数N、M、およびTを含む.以下のM行は、ts時刻番号idの出前店が注文を受けたことを示す2つの整数tsとidを含む.【出力フォーマット】整数を出力して答えを表します.【サンプル入力】2 6 6/N店数M注文本数T時刻1 1/時刻番号5 2 3 1 6 2 2 1 6 2
【サンプル出力】1【サンプル解釈】6時点で、1号店優先度が3に下がり、優先キャッシュが除去される.2号店は優先順位を6に上げ、優先キャッシュを入れる.だから1店(2番)が優先キャッシュに入っています.【評価用例の規模と約定】80%の評価用例に対して、1≦N;M; T ≤ 10000. すべての評価例について、1≦N;M; T ≤ 100000, 1 ≤ ts ≤ T, 1 ≤ id ≤ N. この問題を解析すると,プロセスを見ずに結果を直接見るので,まず注文数を入力して優先度を増やし,最終的に優先度を比較すればよい.上は私の最初の分析で、もちろん、間違っていて、結果だけを見て、大きな穴です.今改めて分析すると、優先順位が5より大きいため、優先順位を脱退し、3より小さいため、結果を見ることができないのは明らかだ.結果が4であれば、彼は入ったことがないかもしれないし、入ってから4に減ったかもしれないので、私の考えは1つの時刻ごとに遍歴している.

#include "stdafx.h"
#include
using namespace std;
const int  N=100020;
int a[N];//     
int b[6*N]={0};// 6   ；             
int c[N]={0};//          
int _tmain(int argc, _TCHAR* argv[])
{
	int m,n,t;
	cin>>n>>m>>t;
	int ans=0;
	for(int i=0;i>ts>>id;
		b[6*id+ts];//       b   ；
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=1;j<=6;j++)
		if(b[i*6+j]==0)//id i   j      
		{
			if(a[i]!=0)//     0     ；
			a[i]--;
		}
		else
			{
				a[i]=b[i*6+j]*2;//a[i]     2，  a[i]            
				if(a[i]>5)
					c[i]=1;//        5，      ；
				else if(a[i]<=3&&c[i]==1)//  3，      ；
					c[i]=0;
			}
		
	}
	for(int i=0;i<=n;i++)
		if(c[i]==1)
			ans++;//                   ；
	cout<