讨论 / 关键在于排序,n不妨先开大一些
断桥枫雨 2016-08-13 14:57:15
点我顶贴 收藏 删除
下面的是用 c 语言写的,提交了几次,主要是错在快排上,更准确的说是当两个点权值相等的情况时处理不正确,个人认为这正是考察你对快排有没有有理解透彻,程序通过了10个点的测试,仅供参考。

#include <stdio.h>

#include <stdlib.h>

#define N 100000

struct weight_info{

int index;

int weight

};

void quickSort(struct weight_info w[], int low, int high){

int first, last;

struct weight_info key;

if(low >= high){

return;

}

first = low;

last = high;

key = w[first];

while(first < last){

while((first < last && w[last].weight < key.weight) || (first < last && w[last].weight == key.weight && w[last].index > key.index)){

last--;

}

w[first] = w[last];

while((first < last && w[first].weight > key.weight) || (first < last && w[first].weight == key.weight && w[first].index < key.index)){

first++;

}

w[last] = w[first];

}

w[first] = key;

quickSort(w, low, first - 1);

quickSort(w, first + 1, high);

}

void print(struct weight_info w[], int n){

int j = 0;

for(j = 1; j <= n; j++){

if(j != n)

printf("%d ", w[j].index);

else

printf("%d\n", w[j].index);

}

}

int main()

{

int k,n;

int e[11];

struct weight_info w[N];

int i = 0, j = 0;

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

for(i = 1; i <= 10; i++){

scanf("%d", &e[i]);

}

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

w[i].index = i;

scanf("%d", &(w[i].weight));

}

quickSort(w, 1, n);

for(j = 1; j <= n; j++){

w[j].weight += e[(j - 1) % 10 + 1];

}

quickSort(w, 1, n);

print(w, k);

return 0;

}

#1 18046626470@2016-09-21 20:40:46
回复 删除
下面的是用 c 语言写的,提交了几次,主要是错在快排上,更准确的说是当两个点权值相等的情况时处理不正确,个人认为这正是考察你对快排有没有有理解透彻,程序通过了10个点的测试,仅供参考。

#include <stdio.h>

#include <stdlib.h>

#define N 100000

struct weight_info{

int index;

int weight

};

void quickSort(struct weight_info w[], int low, int high){

int first, last;

struct weight_info key;

if(low >= high){

return;

}

first = low;

last = high;

key = w[first];

while(first < last){

while((first < last && w[last].weight < key.weight) || (first < last && w[last].weight == key.weight && w[last].index > key.index)){

last--;

}

w[first] = w[last];

while((first < last && w[first].weight > key.weight) || (first < last && w[first].weight == key.weight && w[first].index < key.index)){

first++;

}

w[last] = w[first];

}

w[first] = key;

quickSort(w, low, first - 1);

quickSort(w, first + 1, high);

}

void print(struct weight_info w[], int n){

int j = 0;

for(j = 1; j <= n; j++){

if(j != n)

printf("%d ", w[j].index);

else

printf("%d\n", w[j].index);

}

}

int main()

{

int k,n;

int e[11];

struct weight_info w[N];

int i = 0, j = 0;

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

for(i = 1; i <= 10; i++){

scanf("%d", &e[i]);

}

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

w[i].index = i;

scanf("%d", &(w[i].weight));

}

quickSort(w, 1, n);

for(j = 1; j <= n; j++){

w[j].weight += e[(j - 1) % 10 + 1];

}

quickSort(w, 1, n);

print(w, k);

return 0;

}

查看更多回复
提交回复