用若干个-1到2的数组成一个最接近D的数(-1<D<2)。过程中不能超过2。
吐槽一下题目，看了半天才看明白。。。。排个序然后背包。。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #define MAXN 205 5 int cas,n,tot,x[MAXN],d[240005]; 6 double x1; 7 int main(){ 8 //freopen("test.in","r",stdin); 9 scanf("%d",&cas); 10 while(cas--){ 11 scanf("%lf%d",&x1,&n); 12 if(x1>0)tot=x1*10000+1e-8; 13 else tot=x1*10000-1e-8; 14 for(int i=0;i<n;i++){ 15 scanf("%lf",&x1); 16 if(x1>0)x[i]=x1*10000+1e-8; 17 else x[i]=x1*10000-1e-8; 18 19 } 20 std::sort(x,x+n); 21 memset(d,0,sizeof d);d[200000]=1; 22 for(int i=0;i<n;i++){ 23 if(x[i]>0){ 24 for(int j=220000-1;j>=x[i];j--) 25 if(d[j-x[i]])d[j]=1; 26 }else{ 27 for(int j=0;j-x[i]<220000-1;j++) 28 if(d[j-x[i]])d[j]=1; 29 } 30 } 31 for(int i=tot+200000,j=tot+200000;;i--,j++){ 32 if(i>=0&&d[i]==1){ 33 printf("%.4f\n",(i-200000.0)/10000); 34 break; 35 }else if(j<220000&&d[j]==1){ 36 printf("%.4f\n",(j-200000.0)/10000); 37 break; 38 } 39 } 40 } 41 return 0; 42 }