|
? ? ? ? 记一次做题插曲，今天在写郑州轻工业oj平台的1187题时发生了一些小错误，在这里记录一下，本来这道题是一道很简单题，我们只需按照价格的从低到高排序，再进行购买数量的判断就能AC这道题，但我不知道脑子除了什么问题搞了1个小时才通过。
? ? ? ? 以下是错误代码(忽略我起的名字😅)：
#include <stdio.h>
struct store
{
?? ?float price;?? ?//单价?
?? ?int remain;?? ??? ?//库存数量?
?? ?float sum;?? ??? ?//总价值?
};
int main(int argc, const char ?*argv[])
{
?? ?int n,m;
?? ?scanf("%d",&n);
?? ?scanf("%d",&m);
?? ?struct store st[m];
?? ?for(int i = 0; i < m; i++) ? ? ?//读入单价和库存数量?
?? ?{
?? ??? ?scanf("%f %d",&st[i].price,&st[i].remain);
?? ??? ?st[i].sum = st[i].price * st[i].remain;
?? ?}
?? ?struct store target;
?? ?int flag;
?? ?struct store temp;
?? ?for(int i = 0; i < m - 1; i++)?? ?//按照价格从低到高对结构体进行排序?
?? ?{
?? ??? ?target = st[i];
?? ??? ?for (int j = i - 1;j < m ; j++)
?? ??? ?{
? ? ? ? ? ? if(target.price > st[j].price)
?? ??? ??? ?{
?? ??? ??? ??? ?target = st[j];
?? ??? ??? ??? ?flag = j;
?? ??? ??? ?}
?? ??? ?}
? ? ?? ?temp = st[i];
? ? ? ? st[i] = st[flag];
? ? ? ? st[flag] = temp;
?? ?}
?? ?int sum = 0,i;
?? ?float spend = 0.0;
?? ?
?? ?for( i = 0; i < m; i++)?? ??? ??
?? ?{
?? ??? ?if((sum + st[i].remain) > n )?? ?//判断是否买到足够数量的糖果?
?? ??? ??? ?break;
?? ??? ?sum += st[i].remain;
?? ??? ?spend += st[i].sum;
?? ?}
?? ?printf("%.2f\n",(spend + st[i].price * (n - sum)));
?? ?return 0;
}
就是这段代码让我搞了1个小时，刚开始我以为是我的判断部分出现了错误，导致不能通过，我看了多次逻辑没有错误，又找了部分数值试了试，都没有问题，当我将判断部分换成其他大佬的写法去提交时，发现依然不对，这时我开始将目光看向了排序函数(可能有大佬初看时就已经发现我的排序函数不对了😭，但我就是傻了，看了几遍没看出来)。
这个排序算法主要不对的地方在38行，就是三杯水交换这一部分，我这个排序的思想是：每次从未排好序的数中选出最小值和无序数组中第一个数进行交换。
错误原因：我忽略了一点，如果当前选取的要比较的值已经是最小值时，由于在第一层for循环中我未对flag进行处理，那么他会和上一次交换时的flag的下标指向的值进行交换，导致排序错误；
所以正确的排序算法应该是：
for(int i = 0; i < m - 1; i++)?? ?//按照价格从低到高对结构体进行排序?
?? ?{
?? ??? ?flag = i;
?? ??? ?target = st[i];
?? ??? ?for (int j = i + 1;j < m ; j++)
?? ??? ?{
?? ??? ??? ?if(target.price > st[j].price)
?? ??? ??? ?{
?? ??? ??? ??? ?target = st[j];
?? ??? ??? ??? ?flag = j;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if(flag != i)
?? ??? ?{
?? ??? ??? ?temp = st[i];
?? ??? ??? ?st[i] = st[flag];
?? ??? ??? ?st[flag] = temp;
?? ??? ?}
?? ?}
应该是上边这种写法，才能保证排序是从小到大排的。
这就是我今天做题时的小插曲，希望能惊醒我自己，能帮助到各位也是很好的！！！
|