數學問題
題目詳情:
給你兩個長度為n的正整數序列分別為{a1,a2,a3...an},{b1,b2,b3...bn},0<ai,bi<=100；
設S=max{x1*a1+x2*a2+x3*a3+...+xn*an,(1-x1)*b1+(1-x2)*b2+(1-x3)*b3+...+(1-xn)*bn}，xi為整數，0<=xi<=1。
請你求出S的最小值。
輸入描述：
輸入包含多組測試數據，以文件結尾。每組測試數據包含三行行，第一行為一個正整數n(0<n<=100);第二行輸入的是ai,第三行輸入的是bi，每兩個數以空格隔開。
輸出描述：
對于每組測試數據輸出相應的答案。
答題說明:
輸入樣例：
3
2 9 4
2 1 8
3
1 2 3
2 1 1
輸出樣例：
4
2
/*思路：a[],b[]數組中對應坐標位置的數據不同則取最小的那個（取到對應的count1,count2中去），相同的數據（存到c[]數組中）待后面動態規劃分組。 動態規劃的依據是，分兩組的差值和 count1與count2的差值最接近然后求結果。
*/
#include "stdio.h"
#include "stdlib.h"
#define maxn 100+10int a[maxn],count1,b[maxn],count2,n;
int c[maxn],len;inline double abs(double x)
{return x>0?x:-1*x;
}int fun(int size)
{int index;double s1,tmp;int *buf=(int *)malloc(sizeof(int)*size);s1=(size-count2+count1)/2.0; //最佳分組中最小一組的和，去與s1最接近的值 buf[0]=0; index=1; tmp=buf[0];for(int i=1;i<=size;i++){buf[i]=0; buf[i]=buf[i-1];for(int j=0;j<len;j++){if(i-c[j]>=0 && buf[i]<c[j]+buf[i-c[j]]){buf[i]=c[j]+buf[i-c[j]];}}if(abs(s1-buf[i])<=abs(s1-tmp)){tmp=buf[i];index=i;}else{break;} // printf("%d ",buf[i]);}return (count2+buf[index])>(count1+size-buf[index])?(count2+buf[index]):(count1+size-buf[index]);
}int main()
{while(scanf("%d",&n) && n>0){int i,sum;for(i=0;i<n;i++){scanf("%d",&a[i]);}for(i=0,len=0,count1=0,count2=0,sum=0;i<n;i++){scanf("%d",&b[i]);if(a[i]<b[i]){count1+=a[i];}else if(a[i]>b[i]){count2+=b[i];}else{c[len++]=a[i];sum+=a[i];}} if(count1>count2){int tmp=count2; count2=count1; count1=tmp;}if(len>0){printf("%d\n",fun(sum));}else{printf("%d\n",count1>count2?count1:count2);}}
}
CSDN挑戰編程交流群：372863405? ? ? ?? ?
