题面 https://www.luogu.org/problem/P1120 题解 #includeiostream #include algorithm #include set #include cstdlib #include cstring #include cstdio using namespace std; int n,a[ 200 ],m,sum,maxt,zushu; struct node{ int v,c;} b[ 200 ]; bool
题面
https://www.luogu.org/problem/P1120
题解
#include<iostream> #include<algorithm> #include<set> #include<cstdlib> #include<cstring> #include<cstdio> using namespace std; int n,a[200],m,sum,maxt,zushu; struct node{ int v,c; } b[200]; bool cmp(int x,int y){ return x>y; } void dfs(int s0,int num,int rest) { if (num==zushu+1) { printf("%d\n",maxt); exit(0); } if (s0>m) return; int i,s=-1,l=s0,r=m,mid; while (l<=r) { mid=(l+r)/2; if (b[mid].v<=rest) s=mid,r=mid-1; else l=mid+1; } if (s==-1) return; if (b[s].v==rest && b[s].c>0) { b[s].c--; dfs(1,num+1,maxt); b[s].c++; } else { for (i=max(s0,s);i<=m;i++) if (b[i].c>0) { b[i].c--; dfs(i,num,rest-b[i].v); b[i].c++; if (rest==maxt) return; } } } int main(){ int i,j,t,cnt=0,mx=0; cin>>n; for (i=1;i<=n;i++){ cin>>t; if (t<=50) a[++cnt]=t; } n=cnt; sort(a+1,a+n+1,cmp); for (i=1;i<=n;i++) sum+=a[i],mx=max(mx,a[i]); cnt=0; for (i=1;i<=n;) { b[++cnt].c=0; b[cnt].v=a[i]; for (j=i;a[j]==a[i];j++) b[cnt].c++; i=j; } m=cnt; for (maxt=mx;maxt<=sum/2;maxt++) if (sum%maxt==0) { zushu=sum/maxt; dfs(1,1,maxt); } printf("%d",sum); }