Main » 2013 October 11 » [模拟赛NOIP2010]摆数字游戏
6:56 AM [模拟赛NOIP2010]摆数字游戏 |
这个贪心写起来好麻烦#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 5010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; struct node{int d,p;}; int cmp(node a,node b){return a.d<b.d;} node P[N]; string st; int n,k; void doit1() { int w=n/P[0].d; int y=n-P[0].d*w; st=""; int i,j; FOR(i,1,w) st+=('0'+P[0].p); int maxp=0,pos; FOR(i,0,w-1) { pos=-1; FOR(j,1,k) if ((P[j].d-P[0].d<=y)&&(P[j].p>P[0].p)) {maxp=P[j].p;pos=j;} if (pos==-1) break; y-=(P[pos].d-P[0].d); st[i]=('0'+maxp); } } void doit2() { int w=n/P[0].d; w--; int tot=P[0].d*w+P[1].d; while (tot>n&&w) { w--; tot=P[0].d*w+P[1].d; } int y=n-tot; int i,j; int maxp=0,pos; if (w) { st='0'+P[1].p; FOR(i,1,w) st+='0'; FOR(i,0,w) { int tt1=(i==0?P[1].p:P[0].p); int tt2=(i==0?P[1].d:P[0].d); pos=-1; FOR(j,1,k) if ((P[j].d-tt2<=y)&&(P[j].p>tt1)) {maxp=P[j].p;pos=j;} if (pos==-1) break; y-=(P[pos].d-tt2); st[i]=('0'+maxp); } }else st="0"; } int main() { cin>>n>>k; int i; P[k+1].d=2E9; FOR(i,0,k) { cin>>P[i].d; P[i].p=i; } sort(P,P+1+k,cmp); if (P[0].p==0) doit2(); else doit1(); cout<<st<<endl; } |
|
|
| Total comments: 0 | |