Hdu 5718 Oracle【贪心】
OracleAccepts: 599 Submissions: 2576 Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) 问题描述 曾经有一位国王,统治着一片未名之地。他膝下有三个女儿。
三个女儿中最年轻漂亮的当属Psyche。她的父亲不确定她未来的命运,于是他来到Delphi神庙求神谕。 神谕可以看作一个不含前导零的正整数n n n。 为了得到真正的预言,他可以将n n n的各个数位重新排列,并将其分成两个不含前导零的正整数。 请你帮助他求出这两个正整数最大的和。如果不存在这样的两个正整数,输出"Uncertain". 输入描述 第一行一个整数T T T (1≤T≤10) (1 le T le 10) (1≤T≤10),代表数据组数。 接下来T T T行,每行一个正整数n n n (1≤n<1010000000) (1 le n < 10 ^ {10000000}) (1≤n<10?10000000?)。 输出描述 对于每组数据,输出一个整数表示最大的和。若不存在一种方案,输出"Uncertain". 输入样例 3 112 233 1 输出样例 22 35 Uncertain Hint 对于第一组数据,最优方案是将112 112 112分成21 21 21和1 1 1,最大的和为21+1=22 21 + 1 = 22 21+1=22。 对于第二组数据,最优方案是将233 233 233分成2 2 2和33 33 33,最大的和为2+33=35 2 + 33 = 35 2+33=35。 对于第三组数据,显然无法将一个数位分成两部分。 建议使用效率较高的读入方式。 思路:1、首先,正整数不包括0.那么10000000000000这样的数据,应该输出Uncertain。 2、如果为了将一个数拆分成两个数并且保证其家和最大,那么其实就是一个长度为n-1的数和一个长度为1的数加和,能够保证数据最大。 3、那么根据刚才贪心的思路,找一个最小的个位数作为长度为1的数,剩下的数再贪心的将其拼接为一个最大的数,然后模拟加和即可。 4、因为正整数不包括0,那么其拆分出来的长度为1的数也不能是0,那么例如1111000这样数的最终解千万别模拟错了。 Ac代码: #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char a[10000500]; int aa[10000500]; int ans[100005000]; int main() { int t; scanf("%d",&t); while(t--) { memset(a,'0',sizeof(a)); memset(aa,sizeof(aa)); scanf("%s",a); int n=strlen(a); if(n==1) { printf("Uncertainn"); continue; } for(int i=0;i<n;i++) { aa[i]=a[i]-'0'; } int dd=0; sort(aa,aa+n); reverse(aa,aa+n); int i=n-1; int pos; int flag=0; while(i>=0) { if(aa[i]==0) { i--; } else { dd=aa[i]; if(i==n-1) { aa[i-1]+=dd; } else { flag=1; } pos=i; break; } } if(i==0) { printf("Uncertainn"); continue; } ans[0]=0; int cont=1; for(int i=0;i<n;i++) { if(i==pos)continue; ans[cont++]=aa[i]; } if(flag==1) { ans[cont-1]+=dd; } i=cont-1; while(i>=0) { if(ans[i]>=10)ans[i]-=10,ans[i-1]+=1; else break; i--; } for(int i=0;i<cont;i++) { if(i==0&&ans[i]==0)continue; printf("%d",ans[i]); } printf("n"); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |