題意

現有n個魚 m個貓 每條貓有吃一條魚所要花去的時間
問最終x分鐘后會有多少只完整的魚 和不完整的魚

分析

很像操作系統的資源調度的問題
這種卡時間點的問題向來都要好好把
每個步驟所發生的時間給他具體化
我們看每只貓吃一條魚花去ci分鐘 而他是在這一分鐘開始的時刻開始吃的
放到時間軸里就是 0-1-2-3-4-… 、
定義時間點表示在ti分鐘之后
所有貓在0時刻開始的時間點申請吃魚
然后在第ci分鐘處吃完 假如這只貓吃一條魚花3分鐘 那么他應該在2，3交界的位置把完成吃完這條魚
如果把時間軸用循環模擬 應該在循環變量為2的時候完成吃完 那么當第3分鐘開始時 也就是3分鐘以后
開始申請吃下一條魚
那么所有的過程模擬下來就是
從開始吃 魚–不完整的魚的數量++
吃完的時候 不完整的魚–
過了下一整點 再開始吃 魚– 不完整魚數量++
那么關于如何模擬吃和完成吃的過程
申請吃可以用個堆 優先選擇吃的快的
完成吃就可以放到一個完成吃的隊列里搞搞

code

#include<bits/stdc++.h> using namespace std; typedef long long ll;int main() {int m,n,x;while(~scanf("%d%d%d",&n,&m,&x)){int y=0;priority_queue<int,vector<int>,greater<int> >eat[3002];vector<int>fis[3003];for(int i=1;i<=m;i++){int t;scanf("%d",&t);eat[0].push(t);}for(int t=0;t!=x;t++){//當前分鐘 吃的過程while(!eat[t].empty()){int to = eat[t].top();//得到此刻申請資源的貓 以及他的速度eat[t].pop();if(n>0){n--,y++;//吃了 把余++if(to==1)fis[t].push_back(to);//設定完成時間else fis[t+to-1].push_back(to);//這里不是+to時間 而是在+to和上一分鐘的交界處完成 我們把他分給上一分鐘}}//當前分鐘 吃完成的過程 fis為當前分鐘末尾處理for(int i=0;i<fis[t].size();i++){int f = fis[t][i];//當前的魚吃完了y--;//吃完了后要接著吃 不過是下一分鐘開始的時候吃eat[t+1].push(f);}//一個i代表 一個完整的分鐘}printf("%d %d\n",n,y);}return 0; }

總結

以上是生活随笔為你收集整理的Hihocoder #1631 : Cats and Fish 模拟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。