很简单的往下贪。
精确度可以对double类型做读入处理成整数。本人采用了字符串转整数。也可以对读入的数(x+1e-4)*100.因为double类型数字保存的是对输入值的尽量精确值,加上1e-4则可保证一定比输入值大一点点,而不影响结果。
#include <set> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 30000; int n; int b[3]; int a[maxn][10]; void get(int I){ int t=0; for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++){ a[I][t++]=(i*b[0]+j*b[1]+k*b[2]); } sort(a[I],a[I]+t); } char str[100]; int get_num(){ char c; int cnt = 0,add=100,f=0,num=0; scanf("%s",str); int len=strlen(str); for(int i=0;i<len;i++){ if(f) {add/=10;} if(str[i]=='.') f=1; else { num=num*10+str[i]-'0'; } } return num*add; } int c[maxn]; int main() { int kase=1; while(scanf("%d",&n)==1&&n){ for(int i=1;i<=n;i++){ b[0]=get_num(); b[1]=get_num(); b[2]=get_num(); get(i); } for(int i=1;i<=n;i++){ scanf("%d",&c[i]); } int fen = 0; bool flag=true; for(int i=1;i<=n;i++){ if(i==1){ fen = a[c[1]][7]; } else if(c[i]>c[i-1]){ int ok=0; for(int j=7;j>=0;j--){ if(a[c[i]][j]<=fen){ fen=a[c[i]][j]; ok=1; break; } } if(!ok){flag=false; break;} } else{ int ok=0; for(int j=7;j>=0;j--){ if(a[c[i]][j]<fen){ fen=a[c[i]][j]; ok=1; break; } } if(!ok){flag=false; break;} } } printf("Case %d: ",kase++); if(flag) printf("%.2lf\n",(double)fen/100); else printf("No solution\n"); } return 0; }