讨论/技术交流/求助 | 提交一直过不去,但测试结果是对的!/
求助 | 提交一直过不去,但测试结果是对的!

QQ图片20210427204805.png
QQ图片20210427204800.png

提交一直过不去,但测试用例测试一直是对的!
各位朋友有没有遇到相同的问题的
问题ID是1011. 在 D 天内送达包裹的能力
代码如下
int min_ = 1000;

int min(int x, int y) {
if (x <= y) return x;
else return y;
}

int max(int x, int y) {
if (x >= y) return x;
else return y;
}

int max_inArr(int* start, unsigned int size) {
if (size == 1) return *start;
if (size == 2) return max(start[0], start[1]);
int max_ = max(start[1], start[1]);
for (int i = 2; i < size; i++) {
max_ = max(max_, start[i]);
}
return max_;
}

char judge(int* weights, int weightSize, int D, int x) { //二分搜索结点判断函数,由于这个地方不是简单的比大小,需要一个判断函数帮助判断
int sum = 0;
int D_min = 0; //装载量为x时运载货物的最小运载天数
for (int i = 0; i < weightSize; i++) { //利用贪心算法,直到数组遍历完成
sum = sum + weights[i];
if (sum > x) { //超过装载量x时,将最后一天的货物退出,天数加一
D_min = D_min + 1;
i = i - 1;
sum = 0; //求和归零,继续进行遍历
}
}
D_min = D_min + 1;
if (D == D_min) return 'E'; //如果刚好最小运载天数等于形式参数D,则说明当前x值就是运载天数为D时的最小装载量
if (D > D_min) return 'L'; //如果最小运载天数小于形式参数,说明当前x的值较大,大于运载天数为D时的最小装载量,需要在左边继续二分搜索
if (D < D_min) return 'R'; //如果最小运载天数大于形式参数,说明当前x的值较小,小于运载天数为D时的最小运载量,需要在右边继续二分搜索
return 0;
}

int BinarySearch(int* weights,int weightSize,int D,int left, int right){
if (left > right) return min_;
char result = judge(weights, weightSize, D, ((left + right) / 2));
if (result == 'E') {
min_ = min(min_, (left + right) / 2);
return BinarySearch(weights, weightSize, D, left, (left + right) / 2 - 1);
}
else {
if (result == 'R') {
return BinarySearch(weights, weightSize, D, (left + right) / 2 + 1, right);
}
else {
if (result == 'L') {
min_ = min(min_, (left + right) / 2);
return BinarySearch(weights, weightSize, D, left, (left + right) / 2 - 1);
}
else return 0;
}
}
}

int shipWithinDays(int* weights, int weightsSize, int D) {
int sum = 0;
for (int i = 0; i < weightsSize; i++) {
sum = sum + weights[i];
}
if (D == 1) { //先考虑简单情况,如果天数只有一天,则最大装载量应该为数组元素的和
return sum;
}
else { //采用二分搜索思想,将问题转化为判定问题
int left = max_inArr(weights, weightsSize); //设置二分搜索边界,左边界为数组中最大的元素
int right = sum; //右边界为数组所有元素的和
return BinarySearch(weights, weightsSize, D, left, right);
}
}

共 1 个回复

确实稀奇,测试显示是160,但是提交变成了3。猜测可能是地址空间变化之类的,俺也不懂,等大佬回复吧。

读了一下代码,稍稍发现点问题:

  1. 代码可以放在代码块里,方便别人看
  2. 你的min_我个人觉得取得有点小,如果本身货物就很重,1000可能不够
  3. max_inArr函数中,应该是int max_ = max(start[0], start[1]);
  4. 有两个地方涉及到了完全不会触发的return 0,不知道是咋考虑的

放一下排好版的代码,方便后来人阅读+测试

int min_ = 1000;

int min(int x, int y) {
    if (x <= y) return x;
    else return y;
}

int max(int x, int y) {
    if (x >= y) return x;
    else return y;
}

int max_inArr(int* start, unsigned int size) {
    if (size == 1) return *start;
    if (size == 2) return max(start[0], start[1]);
    int max_ = max(start[0], start[1]);
    for (int i = 2; i < size; i++) {
        max_ = max(max_, start[i]);
    }
    return max_;
}

char judge(int* weights, int weightSize, int D, int x) { //二分搜索结点判断函数,由于这个地方不是简单的比大小,需要一个判断函数帮助判断
    int sum = 0;
    int D_min = 0; //装载量为x时运载货物的最小运载天数
    for (int i = 0; i < weightSize; i++) { //利用贪心算法,直到数组遍历完成
        sum = sum + weights[i];
        if (sum > x) { //超过装载量x时,将最后一天的货物退出,天数加一
            D_min = D_min + 1;
            i = i - 1;
            sum = 0; //求和归零,继续进行遍历
        }
    }
    D_min = D_min + 1;
    if (D == D_min) return 'E'; //如果刚好最小运载天数等于形式参数D,则说明当前x值就是运载天数为D时的最小装载量
    if (D > D_min) return 'L'; //如果最小运载天数小于形式参数,说明当前x的值较大,大于运载天数为D时的最小装载量,需要在左边继续二分搜索
    if (D < D_min) return 'R'; //如果最小运载天数大于形式参数,说明当前x的值较小,小于运载天数为D时的最小运载量,需要在右边继续二分搜索
    return 0;
}

int BinarySearch(int* weights,int weightSize,int D,int left, int right){
    if (left > right) return min_;
    char result = judge(weights, weightSize, D, ((left + right) / 2));
    if (result == 'E') {
        min_ = min(min_, (left + right) / 2);
        return BinarySearch(weights, weightSize, D, left, (left + right) / 2 - 1);
    }
    else {
        if (result == 'R') {
            return BinarySearch(weights, weightSize, D, (left + right) / 2 + 1, right);
        }
        else {
            if (result == 'L') {
                min_ = min(min_, (left + right) / 2);
                return BinarySearch(weights, weightSize, D, left, (left + right) / 2 - 1);
            }
            else return 0;
        }
    }
}

int shipWithinDays(int* weights, int weightsSize, int D) {
    int sum = 0;
    for (int i = 0; i < weightsSize; i++) {
        sum = sum + weights[i];
    }
    if (D == 1) { //先考虑简单情况,如果天数只有一天,则最大装载量应该为数组元素的和
        return sum;
    }
    else { //采用二分搜索思想,将问题转化为判定问题
        int left = max_inArr(weights, weightsSize); //设置二分搜索边界,左边界为数组中最大的元素
        int right = sum; //右边界为数组所有元素的和
        return BinarySearch(weights, weightsSize, D, left, right);
    }
}