优先队列太好用了手写啥呀
poj1456 经过贪心专题的洗礼以后这题根本就不叫题啊。。。按时间大到小排每次取最大就好
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; struct node { int v,d; }a[11000]; bool cmp(node n1,node n2){return n1.d>n2.d;} priority_queue<int>q; int main() { int n,mmax=0; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d%d",&a[i].v,&a[i].d), mmax=max(mmax,a[i].d); sort(a+1,a+n+1,cmp); int tp=1,ans=0; while(!q.empty())q.pop(); for(int i=mmax;i>=1;i--) { while(tp<=n&&a[tp].d>=i) q.push(a[tp].v), tp++; if(!q.empty()) ans+=q.top(), q.pop(); } printf("%d ",ans); } return 0; }
poj2442 这题还是很有价值的。一开始想了个貌似很对的做法，就是把每一行排完序和第一个作差，差值压进小根堆里面，堆顶出来以后和之前出去的合并，然后用两个LL的变量记录状态判重，结果后来发现只要m>=3就会有循环，然后就会重复，强行map判定又会多删。最后就是两两合并，因为只有两行所以可以省掉一个n，就能过了。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; int a[2100],c[2][2100]; struct node { int x,y,d1,d2;bool op; friend bool operator>(node n1,node n2) { return (n1.d1+n1.d2)>(n2.d1+n2.d2); } };priority_queue<node,vector<node>,greater<node> >q; void ins(int x,int y,int d1,int d2,bool op) { node t; t.x=x;t.y=y;t.op=op; t.d1=d1;t.d2=d2;q.push(t); } void merge(int n) { while(!q.empty())q.pop(); ins(1,1,c[0][1],c[1][1],false); for(int i=1;i<=n;i++) { node t=q.top();q.pop(); a[i]=t.d1+t.d2; if(t.x<n)ins(t.x,t.y+1,c[0][t.x],c[1][t.y+1],true); if(t.y<n&&t.op==false)ins(t.x+1,t.y,c[0][t.x+1],c[1][t.y],false); } for(int i=1;i<=n;i++)c[0][i]=a[i]; } int main() { int T; scanf("%d",&T); while(T--) { int m,n,sum=0; scanf("%d%d",&m,&n); for(int j=1;j<=n;j++)scanf("%d",&a[j]); sort(a+1,a+n+1);sum+=a[1]; for(int j=1;j<=n;j++)c[0][j]=a[j]-a[1]; for(int i=2;i<=m;i++) { for(int j=1;j<=n;j++)scanf("%d",&a[j]); sort(a+1,a+n+1);sum+=a[1]; for(int j=1;j<=n;j++)c[1][j]=a[j]-a[1]; merge(n); } for(int i=1;i<n;i++)printf("%d ",sum+c[0][i]); printf("%d ",sum+c[0][n]); } return 0; }
bzoj1150: [CTSC2007]数据备份Backup ->环形版 bzoj2151: 种树
合并果子就算了
bzoj4198 这个想一想就可以发现对应一个k叉的哈夫曼树嘛。。深度较小的话就加一个变量表示合并的次数，相同情况合并合并次数较小的就好。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; typedef long long LL; struct node { LL x;int id,mr; friend bool operator>(node n1,node n2) { if(n1.x==n2.x)return n1.mr>n2.mr; return n1.x>n2.x; } };priority_queue<node,vector<node>,greater<node> >q; void insert(LL x,int id,int mr) { node t; t.x=x;t.id=id;t.mr=mr; q.push(t); } struct edge { int x,y,next; }a[1100000];int len,last[1100000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int li,deper;LL sum,c[110000]; void dfs(int x,int dep) { if(x<=li) { sum+=((LL)dep)*c[x]; deper=max(dep,deper); return ; } for(int k=last[x];k;k=a[k].next) { int y=a[k].y; dfs(y,dep+1); } } int main() { int n,k;node t,p; scanf("%d%d",&n,&k);li=n; for(int i=1;i<=n;i++) scanf("%lld",&c[i]), insert(c[i],i,0); while((n-1)%(k-1)!=0) insert(0,++n,0); int cc=(n-1)/(k-1); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=cc;i++) { t.x=0;t.id=++n;t.mr=1; for(int j=1;j<=k;j++) { p=q.top();q.pop(); t.x+=p.x;t.mr+=p.mr; ins(t.id,p.id); } q.push(t); } sum=0;deper=0; dfs(q.top().id,0); printf("%lld %d ",sum,deper); return 0; }