[C++知识库]周总结（第一周）

1.我的错题反思：

线性随机键盘、

/*?????? 思路解析：

先输入n，再一次输入第一个、第二个字符串，利用两个for循环，用第一个字符串对第二个字符串依次定位，依次存放再数组中，再依次累加前后项相减项，输出结果。*/

#include <stdio.h>

#include <string.h>

#include <math.h>

int main() {

int n;

char str[1000];……………………存放第一个字符串

char ch[1000];……………………存放第二个字符串

int num[100];…………………………存为定位的地址

int c;

int sum = 0;

int i, j, k, h, l;

scanf("%d", &n);

for (i = 0; i < n; i++) {

sum = 0;

l = 0;

F = 1;

scanf("%s", str);…………………………依次输入两个字符串

scanf("%s", ch);

for (j = 0; j < strlen(ch); j++)………………第二个字符串，用短的作为被定位者

?{

for (k = 0; k < strlen(str); k++)………………利用第一个字符串进行定位

?{

if (ch[j] == str[k])

{

num[l++] = k + 1;………………定位字符的位置，并保存。

}

}

}

(错误项，已改正)

for (h = 1; h < l; h++)………………从第一项开始，避免数组越界，跳过第一项开始。

?{

sum += abs(num[h] - num[h - 1]);

}

printf("%d\n", sum);

}

return 0;

}

反思:

错在累加相减项，原为“for (h = 1; h < l; h++)”未考虑数组的越界，当h=0时“sum += abs(num[0] - num[-1]);”，存在越界值num【-1】，再dev c++上虽然能通过，但在pta上会出现乱码，故改为从第二项开始，跳过第一项，避免了越界。

2.有得：

卖沙，卖沙，三块钱一斤，十块钱三斤

思路：

先利用结构体构建贮存数组，再利用快排对单价进行排序，之后再累加求值

#include <stdio.h>

#include <math.h>

struct shazi ??????????????????????????????????……………………结构体，先命名

{

int zs;???????????????????????????????? …………………………设置变量，总数量

int zj;???????????????????????????????????? …………………………设置变量，总价值

double dj;??????????????????????????????? …………………………设置变量，每种单价

};struct shazi num[1000];??????????????????? …………设置数组num【】???????????????

void QuickSort(struct shazi *num, int xiao, int da)…………调用无参函数

……………………num为结构体类型，必须声明，struct+结构体名称+数组名

比较详解：

本次比较，与原版快排不同，比较的每种沙子的单价，交换的是结构体变量

（本体结构体变量num附带了总价值、总数量、单价）

{????

if (xiao < da) ………………判断是否输入错误

{???? ???

int i = xiao;……………………相当于第一个的下标

int j = da;……………………相当于最后一个的下标

double k = num[xiao].dj;????????????????? ……………………定义最小值为第一个值。

struct shazi p=num[xiao];??????????????? ……………………定义一个结构体变量p。

while (i < j)????????????????????????????????? ___快排算法核心

?{

while (i < j && num[j].dj >k)

{

j--;

}

if (i < j)

{

num[i++]= num[j];

}

while (i < j && num[i].dj< k)

{

i++;

}

if (i < j)

{

num[j--] = num[i];

}

}

num[i]= p;

QuickSort(num, xiao, i - 1);………………返回每次最小值

QuickSort(num, i + 1, da);………………返回每次最大值

}????? ??????

}????

int main() {

int n;

int i, j;

int bag;

double sum = 0;

scanf("%d %d", &n, &bag);

for (i = 0; i < n; i++)

?{

scanf("%d %d", &num[i].zs, &num[i].zj);……………………结构体输入格式

num[i].dj = (1.0 * num[i].zj) / (1.0 * num[i].zs);………………强制类型转换int~~double

}

QuickSort(num, 0, n - 1);………………………………调用函数，只用输入函数名

???

for (i = n-1; i >=0; i-- )……………………逆向输出，更改排序为从大到小，优先取大值

{

if (num[i].zs < bag) …………………………简单累加

{

bag -= num[i].zs;

sum += num[i].zj;

}

else

{

sum += bag * num[i].dj;

break;

}

}

printf("%.2lf", sum);

return 0;

}

注意：

本题要求时间较短，所以不能用冒泡算法…………只能用快排之类的短时间排序方法。

快排交换数据，一定是比较沙子的单价，交换沙子的所有变量。