題目描述
現在現在有一台機器,這台機器可以接收兩種形式任務:(1)任務清單,任務清單裡面有N個任務,對于第i個任務,機器在Ti時間開始執行,并在1個機關時間内做完。(2)臨時任務,機器可以在任意時間接收一個臨時任務,但任務清單裡面的任務優先級要高于臨時任務,也就是說當機器空閑的時候才會執行臨時任務。
現在機器已經接收一個任務清單。接下來會有M個臨時任務,我們想知道每個臨時任務何時被執行。為了簡化問題我們可以認為這M個臨時任務是獨立無關即任務是可以同時執行的,互不影響的。
輸入
輸入資料有多組,每組資料第一行包括兩個整數N和M(1<=N, M<=10^5)。
接下來一行有N個不同數字T1,T2,T3…..TN(1<=T1
接下來又M行,每行一個數字Qi(1<=Qi<=10^9),表示第i個臨時任務的的接收時間。
樣例輸入
5 6
1 2 3 5 6
3
2
1
4
5
6
輸出
對于每個臨時任務,輸出它被執行的時間。
樣例輸出
4
4
4
4
7
7
時間限制
C/C++語言:2000MS其它語言:4000MS
記憶體限制
思路分析
任務清單裡的任務都是有序的,而臨時任務時間表裡的任務無序的,隻要在有序任務裡找到對應時間點的或後續的空閑時間點就可以安排臨時任務。且臨時任務是無關的,這樣的話就可以選擇對臨時任務獨立處理。對于臨時變量,我們可以先進行二分查找,若沒有找到該點,這任務剛好可以安排到這點進行。若找到該點,傳回該點位置後以此檢索下一個空閑點、最近的空閑點就是安排臨時任務點。
#include<iostream>
#include<sstream>
#include<stdio.h>
using namespace std;
int midfind(int data[],int low,int high,int x);
int main(){
int n,m,a,b;
cin>>n>>m;
int data[];
int res;
//c++ cin 輸入以回工廠中的房間隔,采用輸入字元串處理
cin.ignore();//清空緩存區,不然不能有效讀取
string line;
getline(cin,line);
istringstream iss(line);
for(int i=;iss>>a;i++)
{
data[i]=(a);
iss.clear();//清空緩存區
}
// c輸入 d,s以空白符間隔(空格,回車 )
// for(int i=0;i<n;i++){
//scanf("%d",data+i);
// }
for(int j=;cin>>b;j++)
{
int finders=midfind(data,,n-,b);
if(finders==-) {
res=b;//若沒有該點,這任務安排時間即為臨時任務配置設定時間
}else{
while(b++==data[finders++]){}
res=--b;//若有該點,則任務安排時間以此順延,直到下一個空閑點
}
cout<<res<<endl;
}
}
}
//遞歸算法 算法思路清晰,但是多次遞歸調用棧空間易不足
int midfind(int data[],int low,int high,int x)
{
if(low>high) return -;
int mid=(high + low) / ;
if(data[mid]>x)
{
return midfind(data,low,mid-,x);
}else if(data[mid]==x){
return mid;
} else{
return midfind(data,mid+,high,x);
}
}
//非遞歸算法,編寫複雜,效率高[這裡寫連結内容](http://blog.csdn.net/luojinping/article/details/6900768)
int midfind(int data[],int low,int high,int x)
{
int mid=-;
while(low<=high)
{
mid=(low+high)/;
if(data[mid]==x) {
return mid;
}else if(data[mid]>x){
high=mid-;
}else{
low=mid+;
}
}
return mid;
}
C語言中scanf函數與空格回車
遞歸與非遞歸的比較