n个人每个人有不同数值的钱,需要凑出y钱,并且使每个人剩余下来的钱尽可能一样多。

Question

n个人每个人有不同数值的钱,需要凑出y钱,并且使每个人剩余下来的钱尽可能一样多，钱只能是整数。例如有ABCD4个人，钱数分别是4,3,2,1，然后需要凑5元。那么结果应该是A出3元B出2元，CD不用出，生下来就是A1B1C2D1，钱多的先出去，要使得每个人剩下来的钱尽可能一样多

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

#include <stdio.h>
int main(){
    int n,y;
    scanf("%d%d",&n,&y);
    int a[n],b[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
    }
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=a[i]+b[i];
    }
    if(sum<y){
        printf("No");
        return 0;
    }
    int c[sum/2+1]={};
    int i,j,k,l,m,n;
    for(i=0;i<=sum/2;i++){
        c[i]=i;
    }
    for(k=1;k<sum/2+1;k++){
        l=k;
        m=0;
        while(m<c[l]){
            m++;
            j=c[m]-k;
            if(j>y)break;
            k=j;
            m++;
        }
        if(l==m-1){
            c[k]=l;
        }else{
            int tmp=l;
            l=m-1;
            m=tmp;
        }
    }
    for(i=0;i<n;i++){
        if(a[i]+b[i]!=c[y-a[i]-b[i]]){
            printf("No");
            return 0;
        }
    }
    printf("Yes");
}