东华oj自用 76-80（★）

最大效益

问题描述

明明的爸爸开了一家小公司，公司里有5名职员。今天，公司接待了5位客户。明明的爸爸知道，和任何一位客户谈判并签下合同都要花一整天的时间，而他又希望在一天之内，和这5位客户都签好合同。因此，明明的爸爸要求公司里的5名职员分别与1位客户谈判。 明明的爸爸也知道，这5名职员和5位客户的性格各不相同。因此，不同的职员与不同的客户谈判，会给公司带来不同的经济效益。他现在要做出一个决策，让5名职员分别与哪位客户谈判，才能让公司今天的总经济效益最大。 明明的爸爸首先做了一张5行5列的效益表，如下所示： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 在这张效益表中，每行代表一名公司职员，每列代表一个客户，每行中的5个数字就表示了当该行所代表的公司职员和每位客户谈判时所能产生的效益。明明的爸爸就要通过这张效益表来决定哪位职员与哪位顾客谈判，然后能够使公司的效益最大。就拿上面这张表来看，由于无论哪位职员与哪位客户谈判，所产生的效益都是1，因此最大的效益就是5。这是最简单的一种情况，但是当效益表里的数字变得复杂，就很难进行选择，到底哪种组合方式才是最优的。因此明明的爸爸求助于你，帮助他解决这个问题。 明明的爸爸的问题可以归结为：给你一张5行5列的效益表，表中的数字均为大于等于0的整数，要求在这张表中选出5个数字，使这5个数字的和最大。（注：这5个数字分别来自表中的不同行不同列，即同一行只能选择一个数字，同一列也只能选择一个数字。）

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据。每组测试数据占5行；每行包含5个正整数；第i行的第j个正整数Aij代表第i名职员与第j位客户谈判能为公司带来的经济效益（0≤Aij≤100, 1≤i,j≤5）。每组测试数据与其后一组测试数据之间没有任何空行；第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数s，即这一天中公司的最大可能总经济效益。例如：当测试数据中的所有Aij（1≤i,j≤5）均为1时，运算结果s应为5。输出时，每组运算结果s单独占一行，其行首和行尾都没有任何空格或其他任何字符；每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注：通常，显示屏为标准输出设备。

解题思路：

贪心算法，每次选择一个最大的数，检查这个数所在的行和列是否已经选过，如果选过置为0重新找次大数，没有选过则选择，并把这一行和这一列标记为已选过。

初始代码：

0.9/1  三个测试用例通过一个

#include <stdio.h>

int main(){
int a,b,c,d,e;
int x[5][5];

for(int i=0;i<5;i++){
scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
for(int j=0;j<5;j++){
x[i][0]=a;
x[i][1]=b;
x[i][2]=c;
x[i][3]=d;
x[i][4]=e;
}
}

int hang[5]={0};
int lie[5]={0};
int count=0;
int sum=0;

while(count<5){
int found=0;
while(found==0){
int max=-1;
int p=0;
int q=0;
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
if(x[i][j]>max){
max=x[i][j];
p=i;
q=j;
}
}
}
if(hang[p]!=1 && lie[q]!=1){
sum+=max;
hang[p]=1;
lie[q]=1;
x[p][q]=0;
found=1;
}else{
x[p][q]=0;
}
}
count++;
}

printf("%d",sum);
return 0;
}

二次调整

已AC

题中要求有多组输入

        while(scanf("%d %d %d %d %d",&a,&b,&c,&d,&e) != EOF){         // 读第0行         for(int j=0;j<5;j++){             x[0][0]=a;             x[0][1]=b;             x[0][2]=c;             x[0][3]=d;             x[0][4]=e;         }                  // 读剩下的4行         for(int i=1;i<5;i++){             scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);             for(int j=0;j<5;j++){                 x[i][0]=a;                 x[i][1]=b;                 x[i][2]=c;                 x[i][3]=d;                 x[i][4]=e;             }         }

三次调整

贪心算法只看到眼前的最大值，没看到选了这个大数，会牺牲掉后面更多的大数。

因此建议使用必须用暴力枚举/匈牙利算法/DFS

AC代码：

贪心算法版本

#include <stdio.h>

int main(){
int a,b,c,d,e;
int x[5][5];

while(scanf("%d %d %d %d %d",&a,&b,&c,&d,&e) != EOF){
// 读第0行
for(int j=0;j<5;j++){
x[0][0]=a;
x[0][1]=b;
x[0][2]=c;
x[0][3]=d;
x[0][4]=e;
}

// 读剩下的4行
for(int i=1;i<5;i++){
scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
for(int j=0;j<5;j++){
x[i][0]=a;
x[i][1]=b;
x[i][2]=c;
x[i][3]=d;
x[i][4]=e;
}
}

int hang[5]={0};
int lie[5]={0};
int count=0;
int sum=0;

while(count<5){
int found=0;
while(found==0){
int max=-1;
int p=0;
int q=0;
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
if(x[i][j]>max){
max=x[i][j];
p=i;
q=j;
}
}
}
if(hang[p]!=1 && lie[q]!=1){
sum+=max;
hang[p]=1;
lie[q]=1;
x[p][q]=0;
found=1;
}else{
x[p][q]=0;
}
}
count++;
}

printf("%d\\n",sum);
}
return 0;
}

dfs算法版本

#include <stdio.h>

int x[5][5];
int used_col[5]; // 记录每一列是否被选过
int max_sum; // 记录最大效益

// DFS函数：row表示当前要选第几行，sum表示当前已经得到的效益和
void dfs(int row, int sum){
// 选完5行了，记录最大值
if(row == 5){
if(sum > max_sum){
max_sum = sum;
}
return;
}

// 尝试当前row行的每一列
for(int col = 0; col < 5; col++){
if(used_col[col] == 0){ // 如果这一列还没被选过
used_col[col] = 1; // 标记这一列已选
dfs(row + 1, sum + x[row][col]); // 去选下一行
used_col[col] = 0; // 回溯：取消标记
}
}
}

int main(){
int a,b,c,d,e;

// 多组输入
while(scanf("%d %d %d %d %d",&a,&b,&c,&d,&e) != EOF){
// 第0行 – 完全保留你的输入代码风格
for(int j=0;j<5;j++){
x[0][0]=a;
x[0][1]=b;
x[0][2]=c;
x[0][3]=d;
x[0][4]=e;
}

// 读剩下的4行
for(int i=1;i<5;i++){
scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
for(int j=0;j<5;j++){
x[i][0]=a;
x[i][1]=b;
x[i][2]=c;
x[i][3]=d;
x[i][4]=e;
}
}

// 初始化
for(int i=0;i<5;i++){
used_col[i] = 0;
}
max_sum = 0;

// 从第0行开始，当前和为0
dfs(0, 0);

printf("%d\\n", max_sum);
}
return 0;
}

错误反思：

螺旋方阵（★）

问题描述

明明在上学的时候，参加数学兴趣班。在班上，老师介绍了一种非常有趣的方阵，称之为螺旋方阵。该方阵一共由n×n个正整数构成（我们称之为n阶螺旋方阵），即共有n行n列。

方阵中的数字从1开始递增，数字的排序规则是从左上角出发由1开始排序，并按顺时针方向旋进，即先排最外面的一圈，然后排里面的一圈，以此类推，直到排到最后一个数为止。

例如一个4阶的螺旋方阵，一共有4×4=16个正整数构成，数字从1递增到16，最后排出来的方阵如下：

 1  2  3  4

12 13 14  5

11 16 15  6

10  9  8  7

明明回家后想自己动手构造这样的螺旋方阵。他从n=1开始构造，但是他发现当n越来越大时，螺旋方阵的复杂性就越高，然后构造出来的方阵就越容易出错。为了降低构造方阵的出错率，提高构造速度，明明就求助于你，请你帮他写一个程序，来构造螺旋方阵。 明明的问题可以归结为：给你一个正整数n，请你按题目描述中所述的方法，构造出n阶的螺旋方阵。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行仅有一个正整数n（1≤n≤10），即所要构造的螺旋方阵的阶数。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个n阶的螺旋方阵，方阵中的数字用一个空格隔开，具体形式请参考输出样例。每组运算结果与其后一组运算结果之间有一个空行，最后一组运算结果之后没有空行。 注：通常，显示屏为标准输出设备。

解题思路：

（看完讲解）

法一：（使用）方向切换法，按照右下左上的顺序，一旦一个方向走不动就退出此方向的循环，换到下一个方向继续走。

即

while num < n*n:     // 向右：直到碰到边界或已填数字     while 可以向右:         向右移动一格，填数字

    // 向下：直到碰到边界或已填数字     while 可以向下:         向下移动一格，填数字

    // 向左：直到碰到边界或已填数字     while 可以向左:         向左移动一格，填数字

    // 向上：直到碰到边界或已填数字     while 可以向上:         向上移动一格，填数字

法二：边界收缩法，初始化边界，在边界范围内填数，超出边界则换方向，同时边界缩小

初始化四个边界 top=0, bottom=n-1, left=0, right=n-1 num = 1

while num <= n*n:     // 1. 向右：top行，left→right     for j from left to right:         matrix[top][j] = num++     top++  // 上边界下移          // 2. 向下：right列，top→bottom     for i from top to bottom:         matrix[i][right] = num++     right–  // 右边界左移          // 3. 向左：bottom行，right→left     if top <= bottom:         for j from right down to left:             matrix[bottom][j] = num++         bottom–  // 下边界上移          // 4. 向上：left列，bottom→top     if left <= right:         for i from bottom down to top:             matrix[i][left] = num++         left++  // 左边界右移

初始代码：

法一

#include <stdio.h>

int main(){
int n;
while(scanf("%d",&n)!=EOF){
int a[11][11]={0};

int now=1;
int x=0,y=0;
a[0][0]=1;
while(now<n*n){
//向右，退出循环说明到右边界
while(y+1<n && a[x][y+1]==0){
a[x][++y]=++now;
}
//向下，退出循环说明到下边界
while(x+1<n && a[x+1][y]==0){
a[++x][y]=++now;
}
//向左，退出循环说明到左边界
while(y-1>=0 && a[x][y-1]==0){
a[x][–y]=++now;
}
//向上，退出循环说明到上边界
while(x-1>=0 && a[x-1][y]==0){
a[–x][y]=++now;
}
}

for(int i=0;i<n;i++){
int first=1;
for(int j=0;j<n;j++){
if(first==1){
printf("%d",a[i][j]);
first=0;
}else printf(" %d",a[i][j]);
}
printf("\\n");
}
}
return 0;
}

AC代码：

法二

#include <stdio.h>

int main(){
int n;

while(scanf("%d", &n) != EOF){
int a[11][11] = {0};
int top = 0, bottom = n-1, left = 0, right = n-1;
int num = 1;

// 螺旋填充
while(num <= n * n){
// 1. 向右：top行，从left到right
for(int i = left; i <= right; i++){
a[top][i] = num++;
}
top++; // 上边界下移

if(num > n * n) break;

// 2. 向下：right列，从top到bottom
for(int i = top; i <= bottom; i++){
a[i][right] = num++;
}
right–; // 右边界左移

if(num > n * n) break;

// 3. 向左：bottom行，从right到left
if(top <= bottom){
for(int i = right; i >= left; i–){
a[bottom][i] = num++;
}
bottom–; // 下边界上移
}

if(num > n * n) break;

// 4. 向上：left列，从bottom到top
if(left <= right){
for(int i = bottom; i >= top; i–){
a[i][left] = num++;
}
left++; // 左边界右移
}
}

// 输出螺旋方阵
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(j == 0){
printf("%d", a[i][j]);
} else {
printf(" %d", a[i][j]);
}
}
printf("\\n");
}
}
return 0;
}

错误反思：

方块转换（★）

问题描述

一块N x N（1=<N<=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。

写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

#1：转90度：图案按顺时针转90度。

#2：转180度：图案按顺时针转180度。

#3：转270度：图案按顺时针转270度。

#4：反射：图案在水平方向翻转（形成原图案的镜像）。

#5：组合：图案在水平方向翻转，然后按照#1-#3之一转换。

#6：不改变：原图案不改变。

#7：无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个。

比如：

转换前：

 @-@  —  @@-

转换后：  @-@  @–  –@

这种转换采取#1（按顺时针转90度）即可。

注意：图案中的字符“@”和“-”在转90度后，还是“@”和“-”。不要认为“-”转90度后变成“|”。

输入说明

第一行： 单独的一个整数N。

第二行到第N+1行： N行,每行N个字符（不是'@'就是'-'）；这是转换前的正方形。

第N+2行到第2*N+1行： N行,每行N个字符（不是'@'就是'-'）；这是转换后的正方形。

输出说明

单独的一行包括1到7之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

解题思路：

输入原图形和新图形，对比在每个变换下的情况，符合则成立（不会写每种变换之后的坐标）

初始代码：

#include <stdio.h>

int main(){
int N;
scanf("%d",&N);
char a;
char b[11][11]; // 转换前
char c[11][11]; // 转换后

// 读转换前图案
for(int i=0;i<N;i++){
scanf("\\n");
for(int j=0;j<N;j++){
scanf("%c",&a);
b[i][j]=a;
}
}

// 读转换后图案
for(int i=0;i<N;i++){
scanf("\\n");
for(int j=0;j<N;j++){
scanf("%c",&a);
c[i][j]=a;
}
}

// 临时数组，用于存储各种变换后的图案
char temp[8][8];
int match;

// #1: 转90度（顺时针）
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(b[N-1-j][i] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("1");
return 0;
}

// #2: 转180度
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(b[N-1-i][N-1-j] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("2");
return 0;
}

// #3: 转270度（顺时针270 = 逆时针90）
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(b[j][N-1-i] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("3");
return 0;
}

// #4: 反射（水平翻转）
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(b[i][N-1-j] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("4");
return 0;
}

// #5: 组合（先反射，再旋转）
// 先反射，存在temp里
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
temp[i][j] = b[i][N-1-j];
}
}

// 5-1: 反射 + 90度
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(temp[N-1-j][i] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("5");
return 0;
}

// 5-2: 反射 + 180度
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(temp[N-1-i][N-1-j] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("5");
return 0;
}

// 5-3: 反射 + 270度
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(temp[j][N-1-i] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("5");
return 0;
}

// #6: 不改变
match = 1;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(b[i][j] != c[i][j]){
match = 0;
break;
}
}
if(!match) break;
}
if(match){
printf("6");
return 0;
}

// #7: 无效转换
printf("7");
return 0;
}

AC代码：同上

错误反思：

优化建议：读每一行

    for(int i = 0; i < N; i++){         scanf("%s", c[i]);     }

格式符

读取方式

会不会读空格/换行

适用场景

阵列（★）

问题描述

明明在上学的时候，参加数学兴趣班。在班上，老师介绍了一种非常有趣的阵列。

该阵列由n个正整数构成，阵列中的数字从1开始递增，数字的排序规则是从1开始由中间逆时针向外转出，2出现在1的下面，然后直至输出n为止。

例如当n=5的时候，阵列如下：  

  5

1 4

2 3

当n=9时，阵列如下：

7 6 5

8 1 4

9 2 3

当n=10时，阵列如下：

  7 6 5

  8 1 4

  9 2 3

10

明明回家后想自己动手构造这样的阵列。他从n=1开始构造，但是他发现当n越来越大时，阵列的复杂性就越高，然后构造出来的阵列就越容易出错。为了降低构造阵列的出错率，提高构造速度，明明就求助于你，请你帮他写一个程序，来构造这样的阵列。

明明的问题可以归结为：给你一个正整数n，请你按题目描述中所述的方法，构造出阵列。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行仅有一个正整数n（1≤n≤99），即所要构造的阵列的大小。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个大小为n的阵列，阵列中的数字用一个空格隔开，具体形式请参考输出样例： 当n为个位数时，输出的每个数占1位，当n为两位数时，两位数所在的列输出的每个数占2位(不足2位的左边补空格)。 每组运算结果与其后一组运算结果之间有一个空行，最后一组运算结果之后没有任何空行。 注：通常，显示屏为标准输出设备。

解题思路：

参考上题螺旋填充，通过添加步长来限制每一次的步数

初始代码：

#include <stdio.h>
#include <string.h>

int main(){
int n;
int first_case = 1;

while(scanf("%d",&n)!=EOF){
if (!first_case) {
printf("\\n");
}
first_case = 0;

int a[30][30];
memset(a, 0, sizeof(a));

// 中心位置
int x = 15, y = 15;
a[x][y] = 1;
int count = 1;

// 螺旋填充
int len = 1;
while(count < n) {
// 下
for(int i = 0; i < len && count < n; i++) {
x++;
a[x][y] = ++count;
}
if(count >= n) break;

// 右
for(int i = 0; i < len && count < n; i++) {
y++;
a[x][y] = ++count;
}
if(count >= n) break;

len++;

// 上
for(int i = 0; i < len && count < n; i++) {
x–;
a[x][y] = ++count;
}
if(count >= n) break;

// 左
for(int i = 0; i < len && count < n; i++) {
y–;
a[x][y] = ++count;
}
if(count >= n) break;

len++;
}

// 找边界
int min_i = 30, max_i = -1, min_j = 30, max_j = -1;
for(int i = 0; i < 30; i++) {
for(int j = 0; j < 30; j++) {
if(a[i][j] != 0) {
if(i < min_i) min_i = i;
if(i > max_i) max_i = i;
if(j < min_j) min_j = j;
if(j > max_j) max_j = j;
}
}
}

// 输出阵列 – 修正格式
for(int i = min_i; i <= max_i; i++) {
for(int j = min_j; j <= max_j; j++) {
if(a[i][j] != 0) {
if(n >= 10) {
// 两位数的情况，右对齐
printf("%2d", a[i][j]);
} else {
printf("%d", a[i][j]);
}
} else {
if(n >= 10) {
printf(" "); // 两个空格
} else {
printf(" "); // 一个空格
}
}

// 数字之间加空格（除了最后一个）
if(j < max_j) {
printf(" ");
}
}
printf("\\n");
}
}
return 0;
}

AC代码：

格式不对，总有测试用例不通过

错误反思：

注意如何输出最左列为0的多重矩阵

饲料调配（★）

问题描述

农夫约翰从来只用调配得最好的饲料来为他的奶牛。

饲料用三种原料调配成：大麦，燕麦和小麦。他知道自己的饲料精确的配比，在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料（同样都由三种麦子组成），然后将它们混合，来调配他的完美饲料。

给出三组整数，表示 大麦：燕麦：小麦 的比例，找出用这三种饲料调配 x：y：z 的饲料的方法。

例如，给出目标饲料 3：4：5 和三种饲料的比例：

1:2:3

3:7:1

2:1:2

你必须编程找出使这三种饲料用量最少的方案，要是不能用这三种饲料调配目标饲料，输出'NONE'。'用量最少'意味着三种饲料的用量（整数）的和必须最小。

对于上面的例子，你可以用8份饲料1，2份饲料2，和5份饲料3，来得到7份目标饲料： 8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)

以上数字中，表示饲料比例的整数都是小于100（数量级）的非负整数，表示各种饲料的份数的整数都小于100。一种混合物的比例不会由其他混合物的比例直接相加得到。

输入说明

Line 1: 三个用空格分开的整数，表示目标饲料

Line 2..4: 每行包括三个用空格分开的整数，表示农夫约翰买进的饲料的比例

输出说明

输出文件要包括一行，这一行要么有四个整数，要么是'NONE'。前三个整数表示三种饲料的份数，用这样的配比可以得到目标饲料。第四个整数表示混合前三种饲料后得到的目标饲料的份数。

解题思路：

除了枚举没思路

初始代码：AI

#include <stdio.h>

int main(){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int keep[5][5];
int x,y,z;
for(int i=0;i<3;i++){
scanf("%d %d %d",&x,&y,&z);
keep[i][0]=x;
keep[i][1]=y;
keep[i][2]=z;
}

int min_sum = 300; // 最大可能和是3*100
int best_i = -1, best_j = -1, best_k = -1, best_total = -1;
int found = 0;

// 暴力枚举三种饲料的份数
for(int i = 0; i <= 100; i++) {
for(int j = 0; j <= 100; j++) {
for(int k = 0; k <= 100; k++) {
// 如果三种饲料份数都为0，跳过
if(i == 0 && j == 0 && k == 0) continue;

// 计算混合后的总量
int total_x = i * keep[0][0] + j * keep[1][0] + k * keep[2][0];
int total_y = i * keep[0][1] + j * keep[1][1] + k * keep[2][1];
int total_z = i * keep[0][2] + j * keep[1][2] + k * keep[2][2];

// 处理目标比例为0的情况
if(a == 0 && b == 0 && c == 0) {
if(total_x == 0 && total_y == 0 && total_z == 0) {
int sum = i + j + k;
if(sum < min_sum || (sum == min_sum && i < best_i)) {
min_sum = sum;
best_i = i;
best_j = j;
best_k = k;
best_total = 1;
found = 1;
}
}
continue;
}

// 检查是否能整除目标比例
int factor = -1;
int valid = 1;

// 处理每个成分
if(a != 0) {
if(total_x == 0 || total_x % a != 0) {
valid = 0;
} else {
factor = total_x / a;
}
} else {
if(total_x != 0) {
valid = 0;
}
}

if(valid && b != 0) {
if(total_y == 0 || total_y % b != 0) {
valid = 0;
} else {
int temp = total_y / b;
if(factor == -1) {
factor = temp;
} else if(temp != factor) {
valid = 0;
}
}
} else if(valid && b == 0) {
if(total_y != 0) {
valid = 0;
}
}

if(valid && c != 0) {
if(total_z == 0 || total_z % c != 0) {
valid = 0;
} else {
int temp = total_z / c;
if(factor == -1) {
factor = temp;
} else if(temp != factor) {
valid = 0;
}
}
} else if(valid && c == 0) {
if(total_z != 0) {
valid = 0;
}
}

// 检查所有成分的比例因子是否一致且大于0
if(valid && factor > 0) {
int sum = i + j + k;
if(sum < min_sum || (sum == min_sum && i < best_i)) {
min_sum = sum;
best_i = i;
best_j = j;
best_k = k;
best_total = factor;
found = 1;
}
}
}
}
}

// 输出结果
if(found) {
printf("%d %d %d %d\\n", best_i, best_j, best_k, best_total);
} else {
printf("NONE\\n");
}

return 0;
}

AC代码：同上

错误反思：