社区讨论

求助(已经等了3天!!!大佬们帮帮我啊!!!)

灌水区参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@loba60mi
此快照首次捕获于
2023/10/29 17:40
2 年前
此快照最后确认于
2023/11/03 23:37
2 年前
查看原帖

题目:P5017 [NOIP2018 普及组] 摆渡车

30pts30pts 代码 对没错我需要30分代码的解释

问题在代码后面,请往下翻

CPP
#include <bits/stdc++.h>
using namespace std;
int top=0;
int ans=0; 
int n; 
int m; 
int timers[1000001]={0};
int arr[1000001]={0};
int num[1000001]={0};
vector<int> fas;
int minVal=9999999;
int nxt(int t){
    int wait=0;
    while(t++){
        if(num[t]!=0){
            wait=t;
            break;
        }
        if(t>=timers[top-1]){
            return -1;
        }	
    } 
    for(int i=0; i<top; i++){
        if(timers[i]==wait){
            return i;
        }
    }
} 
int have(int a, int b){
    for(int i=a; i<=b; i++){
        if(num[i]!=0){
            return 1;
        }
    }
    return 0;
}
void dfs(int ar){ 
    // ar: 上一次车子到达时间
    // 上一次的发车时间大于最大等待者,那么最大等待者肯定上车了 
    //那就回溯
    if(ar-m>=timers[top-1]){
        minVal=min(ans, minVal); 
        return ;
        // return :对于第i个乘客而言,如果上一次车子到达的时间是ar,返回等待时间 
    } 
    // 如果上一次的发车时间 ~ 到达时间之间没有乘客在等车,
    // 那么获得到达时间之后 ,第一个等车的乘客
    if(have(ar-m+1, ar)==0){
        ar=nxt(ar);
        ar=timers[ar];	
    }
    for(int fa=ar; fa<=ar+m; fa++){
        // 从上次发车到这次发车,这段时间里面所有等车的人的总等待时间
        int rec=0;
        for(int i=0; i<top; i++){
            if(timers[i]>ar-m && timers[i]<=fa){// 确保i乘客的时间在范围内
                rec+=(fa-timers[i])*num[timers[i]];// 等待的时间
            }
        }
        ans+=rec;
        dfs(fa+m);
        ans-=rec;
    } 
}
int main(){
    int t=0;   
    cin>>n>>m;
    for(int i=0; i<=n-1; i++){
        cin>>t;
        if(num[t]==0){
            timers[top++]=t;
        }
        num[t]+=1;
    }
    sort(timers, timers+top);
    dfs(timers[0]); 
    cout<<minVal;
    return 0;
}
求dfs函数中for循环中if的详细解释 具体:每个乘客价值和时间计算的具体操作和思路
来自Chromedome(焦急等待)

回复

5 条回复,欢迎继续交流。

正在加载回复...