程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 270B Multithreading

270B Multithreading

編輯:C++入門知識

                                                                                                       B. Multithreading                                                                                                   time limit per test 2 seconds                                                                                                   memory limit per test 256 megabytes                                                                                                   input      standard input                                                                                                   output     standard output Emuskald is addicted to Codeforces, and keeps refreshing the main page not to miss any changes in the "recent actions" list. He likes to read thread conversations where each thread consists of multiple messages. Recent actions shows a list of n different threads ordered by the time of the latest message in the thread. When a new message is posted in a thread that thread jumps on the top of the list. No two messages of different threads are ever posted at the same time. Emuskald has just finished reading all his opened threads and refreshes the main page for some more messages to feed his addiction. He notices that no new threads have appeared in the list and at thei-th place in the list there is a thread that was at theai-th place before the refresh. He doesn't want to waste any time reading old messages so he wants to open only threads with new messages. Help Emuskald find out the number of threads that surely have new messages. A thread x surely has a new message if there is no such sequence of thread updates (posting messages) that both conditions hold: thread x is not updated (it has no new messages); the list order 1, 2, ..., n changes toa1, a2, ..., an. Input The first line of input contains an integer n, the number of threads (1 ≤ n ≤ 105). The next line contains a list ofn space-separated integers a1, a2, ...,an whereai (1 ≤ ai ≤ n) is the old position of thei-th thread in the new list. It is guaranteed that all of theai are distinct. Output Output a single integer — the number of threads that surely contain a new message. Sample test(s) Input 5 5 2 1 3 4 Output 2 Input 3 1 2 3 Output 0 Input 4 4 3 2 1 Output 3 Note In the first test case, threads 2 and 5 are placed before the thread 1, so these threads must contain new messages. Threads 1, 3 and 4 may contain no new messages, if only threads 2 and 5 have new messages. In the second test case, there may be no new messages at all, since the thread order hasn't changed. In the third test case, only thread 1 can contain no new messages.   想了幾天後發現其實這題只需要找一點,從該點到尾部的所有點是按升序排列的,而這點之前的所有點可認為是 變換的得到的。 [cpp]   #include <stdio.h>   #include <string.h>   #include <math.h>   int a[1000000];   int main()   {       int i,j,n,m,s,t,sta;       scanf("%d",&n);       for(i=0;i<=n-1;i++)       {           scanf("%d",&a[i]);       }       if(n==1)       {           printf("0\n");       }else       {           sta=0;           for(i=1;i<=n-1;i++)           {               if(a[i]<a[i-1])               {                   sta=i;               }           }           printf("%d\n",sta);       }       return 0;   }      

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved