补充
CSDN 阅读体验更佳:【训练题34:贪心排序】G:模仿游戏 | 2021牛客寒假算法基础集训营5
题意
- 有 个怪兽,每个怪兽有出现时间 和类型
有一位男生(泽鸽鸽)和一位女生(叶妹妹)玩游戏,每个人都可以每分钟打败一只怪。
但是女生只有在男生之前打败 类型的怪物之后,才能去打败 类型的怪物。
问你最优分配打败所有怪的最短时间范围
- 样例组数
【思路:第一步】赛内思路 + 赛后过的
- 首先最明显的,每种类型的第一只怪都要男生去打败。
那么最难的问题就是:同时有多种怪都是男生没打败过 (也就是女生无法先打),男生要先选择打败哪个?
凭直觉,哪种怪出现的越多就先打败哪种怪,这样女生才能去帮忙,不然只能光看着。
经过思考之后,先打怪物出现多的或者后续出现多的,不一定是最优解。
我们考虑的是让女生尽量每秒都能打败怪物(女生得多强)
也就是说,如果男生第一次打败了 类型的怪物,女生在什么时候开始就能自己打败 类型的怪了?【思路:第二步】
- 我们记录 表示类型为 怪物的第一次出现时间和第二次出现时间。
我们记录 表示类型为 的怪物还没有打败过,攒了多少数量了。
我们记录 表示目前位置女生可以打的怪物的数量。
我们优先选择的策略如下:
(1)首先女生先打。可以在 里面打一个怪物,,前提是有怪可打。
(2)男生要优先打第一次出现的怪物。这些怪物的第二次出现时间最早的优先。
(3)如果男生打败了第一次出现的怪物类型 ,那么之前所有的 类型的怪物女生都能打败了。也就是 转移到了 里去。
(4)如果目前所有的怪物都不是第一次出现,那男生也在 里面打一个怪物。
这样,代码就出来了:代码
- 时间复杂度:
/* _ __ __ _ _ | | \ \ / / | | (_) | |__ _ _ \ V /__ _ _ __ | | ___ _ | '_ \| | | | \ // _` | '_ \| | / _ \ | | |_) | |_| | | | (_| | | | | |___| __/ | |_.__/ \__, | \_/\__,_|_| |_\_____/\___|_| __/ | |___/ */ const int MAX = 1e5+50; const int INF = 0x3f3f3f3f; vector<int>V[MAX]; struct node{ int p; int v; bool operator <(const node & ND)const{ if(p != ND.p)return p > ND.p; return v < ND.v; } }; priority_queue<node>Q1; bool can[MAX]; int fir[MAX]; int sec[MAX]; int shu[MAX]; int duo; int last; int ans; bool gan(){ if(Q1.empty() && duo == 0)return true; ans++; if(duo)duo--; if(!Q1.empty()){ can[Q1.top().v] = 1; duo += shu[Q1.top().v]; Q1.pop(); }else if(duo)duo--; return false; } int main() { int T;scanf("%d",&T); while(T--){ duo = 0;last = 0;ans = 0; int n;scanf("%d",&n); for(int i = 1;i <= 100000;++i){ fir[i] = INF; sec[i] = INF; shu[i] = 0; can[i] = false; V[i].clear(); } for(int i = 1;i <= n;++i){ int a,b; scanf("%d%d",&a,&b); last = max(last,a); V[a].push_back(b); if(a == fir[b]){ fir[b] = sec[b] = a; }else if(a < fir[b]){ sec[b] = fir[b]; fir[b] = a; }else if(a < sec[b]){ sec[b] = a; } } for(int i = 1;i <= last;++i){ for(auto it : V[i]){ if(i == fir[it]){ Q1.push({sec[it],it}); fir[it] = 0; }else if(can[it]){ duo++; }else { shu[it]++; } } gan(); } ans = last; while(!gan()){;} printf("%d\n",ans); } return 0; }