Description
有一天叶妹妹和泽鸽鸽他们一起参加一个模仿游戏,这个游戏主要任务是打怪兽,每个怪兽都有一个权值,如果两个怪兽的权值相同,那么表示这两个怪兽是同一类型的怪兽。对于任何一个怪兽,只能由一个人去打败它,并且一个人无法同时打两只及两只以上的怪兽。泽鸽鸽和叶妹妹打败任何一个怪兽都只需要花费一分钟,并且他们只能在整数分钟去打怪兽,不能出现小数分钟。由于这是模仿游戏,因此叶妹妹只能模仿泽鸽鸽去打败怪兽。比如,当泽鸽鸽在之前已经打败了权值为 的怪兽后,叶妹妹才能去打权值为
的怪兽(即相同类型的怪兽)。现在给出每个怪兽的出现时间和权值,请你设计一个最优的顺序使得所有怪兽都被打败后的时间最早!
Solution
因为答案是最早的时间,怪兽出现与时间有关,而且时间轴的大小也足够小,所以可以考虑遍历时间来找最大值.
关于贪心策略的话,最简单的是把第一次见到的都给泽鸽鸽打,其他的都给叶妹妹打.但是这样显然会wa,因为泽鸽鸽的时间并没有充分利用(被迫加班?).所以可以在遍历时间时,在该时间结束时去寻找此时的泽鸽鸽是不是在忙,如果没在打怪兽,那么就让他打怪兽,并且在叶妹妹的队列中的个数减一,也就是减一分钟.这样就能保证泽鸽鸽在有空的时候都能帮叶妹妹分担.于是就可以找出最优的时间就是max(泽鸽鸽终止的时间,叶妹妹终止的时间).
Code
#include <bits/stdc++.h> #define endl '\n' typedef long long ll; typedef long double ld; #define endl '\n' #define inf std::numeric_limits<ld>::max() using namespace std; #define Please return #define AC 0 struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); } } _io; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } struct lzh{ int t,a; }; bool cmp(lzh a,lzh b){ if(a.t==b.t){ return a.a<b.a; } return a.t<b.t; } int main() { int t; cin>>t; while(t--){ int n,k; cin>>n; lzh a[n]; for(int i=0;i<n;i++){ cin>>a[i].t>>a[i].a; } vector<int> x[200001]; int vis1=0,vis2=0; int vis[n+1]; memset(vis,0,sizeof(vis)); sort(a,a+n,cmp); for(int i=0;i<n;i++){ x[a[i].t].push_back(a[i].a); } for(int i=1;i<=200000;i++){//开到2e5是为了保证数据不会溢出 for(int j=0;j<x[i].size();j++){ if(vis[x[i][j]]==0){ vis1=max(vis1+1,i); vis[x[i][j]]=i; } else{ if(vis[x[i][j]]==i){ vis2=max(i+1,vis2+1); } else{ vis2=max(i,vis2+1); } } } if(vis1<vis2&&vis1<i){ vis1=i; vis2--; } } //cout<<vis1<<" "<<vis2<<endl; cout<<max(vis1,vis2)<<endl; } Please AC; }