首页 > 试题广场 >

旅行Ⅰ

[编程题]旅行Ⅰ

热度指数：1340 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹出去旅行啦，她准备去 $N$ 个城市旅行，去每个城市的开销是 $A_{i}$ 元。但是牛妹有强迫症，她想在去y城市之前先旅游x城市，于是牛妹列出了这些限制条件list。并且牛妹很节约，她只有 $V$ 元，她每次会选择当前能去的花费最小的城市,如有多个花费一样的则首先去编号小的城市，她想知道她最多能到多少个城市去旅游。

示例1

输入

3,10,[3,7,8],[(1,2)]

输出

说明

先去1号城市再去2号城市，花费为 3+7=10

备注:

城市编号1-N
A[0]代表1号城市的开销
A[1]代表2号城市的开销,以此类推
 ,   
 
,代表去list[i].y城市之前要先去list[i].x城市

算法知识视频讲解

C/C++

nbgao

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型一维数组 A
     * @param ALen int A数组长度
     * @param list Point类vector List
     * @return int整型
     */
    struct P{
        int w, id;
        bool friend operator < (P p1, P p2){
            if(p1.w == p2.w)
                return p1.id > p2.id;
            return p1.w > p2.w;
        }
    };
    int Travel(int N, int V, int* A, int ALen, vector<Point>& list) {
        int inDegree[N+1], cnt=0;
        memset(inDegree, 0, sizeof(inDegree));
        vector<int> G[N+1];
        priority_queue<P> q;
        for(auto &p: list){
            G[p.x].push_back(p.y);
            inDegree[p.y]++;
        }
        for(int i=1;i<=N;i++)
            if(inDegree[i]==0)
                q.push(P{A[i-1], i});
        while(!q.empty()){
            P p = q.top();
            q.pop();
            if(p.w > V)
                break;
            V -= p.w;
            cnt++;
            for(auto &x: G[p.id]){
                inDegree[x]--;
                if(inDegree[x]==0)
                    q.push(P{A[x-1], x});
            }
        }
        return cnt;
    }
};

发表于 2020-08-24 02:48:00 回复(0)

Javascript

机智的阿库娅

91,754595077,[40482,18899,7305,60865,30247,65364,47039,20585,32589,55277,5664,32819,77465,49292,43378,75858,13283,18663,65403,71976,67063,29415,68836,30691,31738,87869,74691,63242,10252,20067,1396,11032,53862,48018,60276,64399,63635,56231,4752,33445,63134,81349,84107,35231,22872,89408,9791,76957,84035,39082,8082,78413,13448,41405,62256,22962,80584,19472,79379,8213,32309,98176,96830,91225,73860,91615,26824,79028,12397,95510,27701,76904,15075,7802,95108,58033,79053,6694,11180,54094,21561,20814,99838,42620,73036,70924,51532,60432,12621,43845,69885],[(31,80),(6,68),(23,42),(11,40),(68,86),(20,42),(5,15),(36,85),(28,78),(60,64),(5,33),(34,58),(41,56),(80,39),(36,52),(75,77),(22,57),(68,20),(41,58),(17,11),(27,12),(46,24),(5,48),(57,33),(8,30),(7,13),(27,17),(11,90),(67,69),(42,13),(8,85),(41,76),(18,81),(48,39),(61,36),(81,6),(87,61),(80,5),(66,7),(62,39),(4,61),(66,81),(34,12),(14,49),(70,2),(1,49),(42,12),(63,43),(6,50),(76,71),(71,33),(12,26),(70,33),(48,44),(4,50),(40,3),(32,75),(46,63),(45,4),(18,52),(87,51),(80,38),(33,18),(24,50),(79,7),(28,21),(3,54),(15,23),(31,71),(88,27),(74,74),(55,30),(27,66),(6,75),(74,86),(76,72),(88,22),(74,57),(2,84),(78,42),(73,65),(14,36),(44,74),(3,78),(12,91),(9,19),(79,42),(33,67),(76,75),(72,58),(24,40),(13,68),(18,66)]

这个用例是不是有问题啊

就算把所有城市都遍历一遍也才花费4410069，远小于754595077，所以预期69是怎么来的

发表于 2023-12-28 15:21:43 回复(5)