sicily_1443 Printer Queue

題目

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

The only printer in the computer science students' union is experiencing an extremely heavy workload. Sometimes there are a hundred jobs in the printer queue and you may have to wait for hours to get a single page of output.

Because some jobs are more important than others, the Hacker General has invented and implemented a simple priority system for the print job queue. Now, each job is assigned a priority between 1 and 9 (with 9 being the highest priority, and 1 being the lowest), and the printer operates as follows.

?The first job J in queue is taken from the queue. 
?If there is some job in the queue with a higher priority than job J, thenmove J to the end of the queue without printing it. 
?Otherwise, print job J (and do not put it back in the queue).

In this way, all those importantmuffin recipes that the Hacker General is printing get printed very quickly. Of course, those annoying term papers that others are printing may have to wait for quite some time to get printed, but that's life.

Your problem with the new policy is that it has become quite tricky to determine when your print job will actually be completed. You decide to write a program to figure this out. The program will be given the current queue (as a list of priorities) as well as the position of your job in the queue, and must then calculate how long it will take until your job is printed, assuming that no additional jobs will be added to the queue. To simplifymatters, we assume that printing a job always takes exactly one minute, and that adding and removing jobs from the queue is instantaneous.

Input

One line with a positive integer: the number of test cases (at most 100). Then for each test case:
?One line with two integers n and m, where n is the number of jobs in the queue (1 ≤ n ≤ 100) and m is the position of your job (0 ≤ m ≤ n ?1). The first position in the queue is number 0, the second is number 1, and so on.
?One linewith n integers in the range 1 to 9, giving the priorities of the jobs in the queue. The first integer gives the priority of the first job, the second integer the priority of the second job, and so on.

Output

For each test case, print one line with a single integer; the number of minutes until your job is completely printed, assuming that no additional print jobs will arrive.

Sample Input

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

Sample Output

1
2
5

題目大意

工作有優(yōu)先級(jí)的打印機(jī)呢袱,求當(dāng)前工作將會(huì)是第幾個(gè)打印出來(lái)的荒给。

思路

按照題目要求峰锁,將低于最高優(yōu)先級(jí)的工作先放到隊(duì)尾即可屹蚊。

代碼

// Copyright (c) 2014 Junjie_Huang@SYSU (SNO:13331087). ALL Rights Reserved.
// 1443.cpp: http://soj.sysu.edu.cn/1443
#include<iostream>
#include<queue>
using std::cin;
using std::cout;
using std::endl;

struct Job {
  // for the position of the jobs can be changed
  // we need to record the initial position of each job.
  int initial_position;
  int priority;
};

int main() {
  int testCase;
  cin >> testCase;
  while (testCase--) {
    int n, position, max_priority = 0;
    std::queue<Job> Que;
    cin >> n >> position;
    for (int i = 0; i < n; i++) {
      Job p;
      p.initial_position = i;
      cin >> p.priority;
      if (max_priority < p.priority) max_priority = p.priority;
      Que.push(p);
    }
    int counter = 0;
    while (Que.front().initial_position != position ||
           Que.front().priority < max_priority) {
      while (Que.front().priority < max_priority) {
        Job temp = Que.front();
        Que.pop();
        Que.push(temp);
      }
      if (Que.front().initial_position == position) break;
      Que.pop();
      counter++;
      n--;
      std::queue<Job> newQue;
      max_priority = 0;
      for (int i = 0; i < n; i++) {
        Job p = Que.front();
        if (max_priority < p.priority) max_priority = p.priority;
        newQue.push(p);
        Que.pop();
      }
      Que = newQue;
    }
    cout << counter + 1 << endl;
  }
  return 0;
}

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市箭券,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖缠导,帶你破解...
    沈念sama閱讀 219,427評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異溉痢,居然都是意外死亡僻造,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,551評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門(mén)孩饼,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)髓削,“玉大人,你說(shuō)我怎么就攤上這事镀娶×⑻牛” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 165,747評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵梯码,是天一觀(guān)的道長(zhǎng)宝泵。 經(jīng)常有香客問(wèn)我,道長(zhǎng)轩娶,這世上最難降的妖魔是什么儿奶? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,939評(píng)論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮罢坝,結(jié)果婚禮上廓握,老公的妹妹穿的比我還像新娘。我一直安慰自己嘁酿,他們只是感情好隙券,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,955評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著闹司,像睡著了一般娱仔。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上游桩,一...
    開(kāi)封第一講書(shū)人閱讀 51,737評(píng)論 1 305
  • 那天牲迫,我揣著相機(jī)與錄音,去河邊找鬼借卧。 笑死盹憎,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的铐刘。 我是一名探鬼主播陪每,決...
    沈念sama閱讀 40,448評(píng)論 3 420
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了檩禾?” 一聲冷哼從身側(cè)響起挂签,我...
    開(kāi)封第一講書(shū)人閱讀 39,352評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎盼产,沒(méi)想到半個(gè)月后饵婆,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,834評(píng)論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡戏售,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,992評(píng)論 3 338
  • 正文 我和宋清朗相戀三年侨核,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蜈项。...
    茶點(diǎn)故事閱讀 40,133評(píng)論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡芹关,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出紧卒,到底是詐尸還是另有隱情侥衬,我是刑警寧澤,帶...
    沈念sama閱讀 35,815評(píng)論 5 346
  • 正文 年R本政府宣布跑芳,位于F島的核電站轴总,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏博个。R本人自食惡果不足惜怀樟,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,477評(píng)論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望盆佣。 院中可真熱鬧往堡,春花似錦、人聲如沸共耍。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,022評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)痹兜。三九已至穆咐,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間字旭,已是汗流浹背对湃。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,147評(píng)論 1 272
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留遗淳,地道東北人拍柒。 一個(gè)月前我還...
    沈念sama閱讀 48,398評(píng)論 3 373
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像屈暗,于是被迫代替她去往敵國(guó)和親拆讯。 傳聞我的和親對(duì)象是個(gè)殘疾皇子剧包,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,077評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容

  • **2014真題Directions:Read the following text. Choose the be...
    又是夜半驚坐起閱讀 9,511評(píng)論 0 23
  • 港囧小記 青春的遺憾 每個(gè)人都有一段青春的回憶,或甜美往果,或苦澀,或遺憾一铅,港囧抓住青春主線(xiàn)陕贮,將青春的遺憾貫穿全劇,上...
    齊小爬閱讀 324評(píng)論 0 1
  • 因時(shí)因地因人而采取的不同管理方法潘飘。 對(duì)于能力差的人肮之,我教你怎么做你就怎么做。 對(duì)于能力強(qiáng)的人卜录,我只要結(jié)果戈擒,中間過(guò)程...
    念美美閱讀 294評(píng)論 3 3