CF118C Fancy Number(模拟)
2021/10/4 23:11:18
本文主要是介绍CF118C Fancy Number(模拟),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
细节还是挺多的
首先找一个使得价值最小的数,注意这个数可能有很多,我们都要把它们存下来,然后尝试更改,注意字典序问题,从后到前还是从前到后更改。
其中有贪心思想:设最后更改为x,则按照x+1,x-1,x+2,x-2...顺序更改。
注意char数组比较字典序不能直接用小于号来比较
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=500005; typedef long long ll; int p,n,k,maxn,pos[N]; ll maxx=1e18; int read(){ int num=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ num=num*10+c-'0'; c=getchar(); } return num*f; } char s[N],anss[N],ss[N]; int xx; int b[N][10],cnt[10],tot[10]; ll solve(int x,int rest){ int res=0; int d=1; while(rest){ if(x+d>9){ d=-d; continue; } if(x+d<0){ d=-(d-1); continue; } if(abs(d)>9) break; if(rest<=cnt[x+d]){ tot[x+d]+=rest; res+=abs(d)*rest; rest=0; } if(rest>cnt[x+d]){ rest-=cnt[x+d]; tot[x+d]+=cnt[x+d]; res+=abs(d)*cnt[x+d]; } if(d<0) d=-(d-1); else d=-d; } return res; } bool cmp(char *a,char *b){ for(int i=0;i<n;i++){ if(a[i]==b[i]) continue; else if(a[i]>b[i]) return 1; else return 0; } return 1; } int main(){ n=read(); k=read(); anss[1]='-'; scanf("%s",s+1); for(int i=1;i<=n;i++){ cnt[s[i]-'0']++; maxn=max(maxn,cnt[s[i]-'0']); } if(maxn>=k){ printf("0\n"); printf("%s",s+1); return 0; } for(int i=0;i<=9;i++){ if(!cnt[i]) continue; memset(tot,0,sizeof(tot)); ll tmp=solve(i,k-cnt[i]); if(maxx>tmp){ maxx=tmp; xx=1; pos[xx]=i; for(int j=0;j<=9;j++) b[xx][j]=tot[j]; } else if(maxx==tmp){ maxx=tmp; pos[++xx]=i; for(int j=0;j<=9;j++) b[xx][j]=tot[j]; } } for(int k=1;k<=xx;k++){ for(int i=1;i<=n;i++) ss[i]=s[i]; for(int i=0;i<=9;i++){ if(i<pos[k]){ if(b[k][i]){ for(int j=n;j>=1;j--){ if(s[j]-'0'==i){ ss[j]=(char)(pos[k]+'0'); b[k][i]--; } if(b[k][i]==0) break; } } } else{ if(b[k][i]){ for(int j=1;j<=n;j++){ if(s[j]-'0'==i){ ss[j]=(char)(pos[k]+'0'); b[k][i]--; } if(b[k][i]==0) break; } } } } if(anss[1]=='-') for(int p=1;p<=n;p++) anss[p]=ss[p]; if(cmp(anss,ss)) for(int p=1;p<=n;p++) anss[p]=ss[p]; } printf("%lld\n",maxx); cout<<anss+1; return 0; }
这篇关于CF118C Fancy Number(模拟)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享