hdu 4398 Template Library Management (贪心 最优调度问题)

Template Library ManagementTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 627 Accepted Submission(s): 189

Problem DescriptionInputOutputSample InputSample OutputAuthorSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 100005#define MAXN 300005#define mod 1000000007#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6typedef long long ll;using namespace std;int n,m,ans,cnt;int a[maxn],pp[maxn];map<int,int>next;struct Node{ int u; bool operator < (const Node &xx)const { return next[u]>next[xx.u]; }}cur;multiset<Node>s;set<int>mys;void solve(){ int i,j,t; ans=0; s.clear(); mys.clear(); for(i=1; i<=m; i++) { if(!next[i]) next[i]=n+1; cur.u=i; mys.insert(i); s.insert(cur); } for(i=1; i<=n; i++) { t=next[a[i]]; cur.u=a[i]; if(mys.find(a[i])!=mys.end()) // 有的话更新 { s.erase(cur); // 这里需要删除了再插入 不然不会帮你排序的 next[a[i]]=pp[t]; s.insert(cur); // 不要以为pp[t]=n+1就不要插了 } else // 没有的话维护set { ans++; next[a[i]]=pp[t]; if(pp[t]>=next[(*s.begin()).u]) continue ; // 小剪枝 mys.insert(a[i]); s.insert(cur); mys.erase((*s.begin()).u); // 每次删除next[]最大的 s.erase(s.begin()); } }}int main(){ int i,j,t; while(~scanf("%d%d",&n,&m)) { for(i=1; i<=n; i++) { scanf("%d",&a[i]); } next.clear(); for(i=n; i>=1; i--) { if(next[a[i]]) t=next[a[i]]; else t=n+1; next[a[i]]=i; pp[i]=t; } pp[n+1]=n+1; solve(); printf("%d\n",ans); } return 0;}/*6 31000 99 86 86 87 9920 31000 99 86 86 87 99 1000 68 86 8 8 8 9 6 8 99 98 97 1000 1000ans:4 10*/