1 [NOIP2004]合并果子
本题应用到了优先队列,这也算是我的第一道优先队列题。
#include<bits/stdc++.h> using namespace std; int main(){ int n,e,a,b,ans=0,c; cin>>n; priority_queue<int,vector<int>,greater<int>> p; for(int i=0;i<n;i++){ cin>>e; p.push(e); } while(p.size()>1){ a=p.top(); p.pop(); b=p.top(); p.pop(); c=a+b; ans+=c; p.push(c); } cout<<ans<<endl; return 0; }
2 Running Median
#include<bits/stdc++.h> using namespace std; int read(){ int x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main(){ int T; T=read(); while(T--){ int n,m; n=read();m=read(); printf("%d %d\n",n,(m+1)/2); priority_queue<int,vector<int>,greater<int>>q1; priority_queue<int>q2; int x; x=read(); q1.push(x); printf("%d ",x); for(int i=2;i<=m;i++){ x=read(); if(x<=q1.top()) q2.push(x); else q1.push(x); if(q1.size()>q2.size()+1){ q2.push(q1.top()); q1.pop(); }else if(q1.size()+1<q2.size()){ q1.push(q2.top()); q2.pop(); } if(i&1){ if(q1.size()>q2.size()) printf("%d ",q1.top()); else printf("%d ",q2.top()); } if(i%20==0) printf("\n"); } printf("\n"); } return 0; }
3 第k小
#include<bits/stdc++.h> using namespace std; int main(){ int x,n,m,k,b; cin>>n>>m>>k; priority_queue<int>q1; while(n--){ cin>>x; q1.push(x); } while(q1.size()>k){q1.pop();} while(m--){ cin>>x; if(x==1){ cin>>b; q1.push(b); while(q1.size()>k){q1.pop();} }else if(x==2){ if(q1.size()!=k) cout<<"-1\n"; else cout<<q1.top()<<endl; } } return 0; }
4 tokitsukaze and Soldier
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct node{ int v,s; }a[N]; bool cmp(node a,node b){ return a.s>b.s; } priority_queue<int,vector<int>,greater<int>>q; int main(){ ios::sync_with_stdio(0); int n; long long sum=0,ans=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i].v>>a[i].s; } sort(a,a+n,cmp); for(int i=0;i<n;i++){ sum+=a[i].v; q.push(a[i].v); while(a[i].s<q.size()){ sum-=q.top(); q.pop(); } ans=max(ans,sum); } cout<<ans<<endl; return 0; }
5 [JSOI2007]建筑抢修
#include<bits/stdc++.h> using namespace std; const int N=150000+10; struct node{ int t1,t2; }a[N]; bool cmp(node x,node y){ return x.t2<y.t2; } priority_queue<int>q; int main(){ int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i].t1>>a[i].t2; sort(a,a+n,cmp); long long sumt=0; for(int i=0;i<n;i++){ sumt+=a[i].t1; q.push(a[i].t1); while(sumt>a[i].t2){ sumt-=q.top(); q.pop(); } } cout<<q.size()<<endl; return 0; }
6 [JSOI2010]缓存交换
7 背包
8 Cut
9 Operating System
10 网络优化
11 小A与任务
12 简单的数据结构
13 老子的全排列呢
#include<iostream> #include<algorithm> using namespace std; int main(){ int a[8]; for(int i=0;i<8;i++){ a[i]=i+1; } do{ for(int i=0;i<8;i++){ printf("%d ",a[i]); } printf("\n"); }while(next_permutation(a,a+8)); return 0; }