当前位置：首页 > news >正文

vue做的网站有什么百度加盟

news 2025/7/19 8:11:12

vue做的网站有什么,百度加盟,广州网站建设美词,网络公司网站http://poj.org/problem?id2431 树上巧妙的思路每次经过一个stop 就相当于获得一次加油的机会但是可以不用这个机会当没油的时候再加这个时候可以加的油最优的方案就是先按油多的加优先队列按按照油降序存储很像蚂蚁那道题巧妙的思维啊！ 1 #include <…

http://poj.org/problem?id=2431

树上巧妙的思路

每次经过一个stop 就相当于获得一次加油的机会但是可以不用这个机会

当没油的时候再加这个时候可以加的油最优的方案就是先按油多的加

优先队列按按照油降序存储

很像蚂蚁那道题巧妙的思维啊！

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 struct Stop
11 {
12     int dis, fuel;
13     bool operator < (Stop s) const
14     {
15         return fuel < s.fuel;
16     }
17 }truck;
18 
19 bool cmp(Stop a, Stop b)
20 {
21     return a.dis > b.dis;
22 }
23 
24 priority_queue<Stop> que;
25 vector<Stop> v;
26 
27 int N, L, P;
28 bool flag = true;
29 int main()
30 {
31     freopen("in.txt", "r", stdin);
32    scanf("%d", &N);
33    while (N--)
34    {
35        int dis, fuel;
36        Stop tmp;
37        scanf("%d%d", &dis, &fuel);
38        tmp.dis = dis;
39        tmp.fuel = fuel;
40        v.push_back(tmp);
41    }
42    sort(v.begin(), v.end(), cmp);
43    scanf("%d%d", &L, &P);
44    truck.dis = L;
45    truck.fuel = P;
46    int j = 0, ans = 0;
47    for (int i = 0; i < v.size(); i++)
48    if (truck.fuel >= (truck.dis - v[i].dis))
49    {
50        que.push(v[i]);
51    }
52    else
53    {
54        i = i-1;
55        if (!que.empty())//如果还有油可以加
56        {
57             truck.fuel += que.top().fuel;
58             que.pop();
59             ans++;
60        }
61        else
62        {
63            printf("-1\n");//这里之前没有直接 退出 而是去设置flag 可能造成了死循环
64            return 0;
65        }
66    }
67     while(flag)
68     {
69         if (truck.dis <= truck.fuel) break;
70         else if (!que.empty())
71         {
72             truck.fuel += que.top().fuel;
73             que.pop();
74             ans++;
75         }
76         else flag = false;
77     }
78    if (flag) printf("%d\n", ans);
79    else printf("-1\n");
80    return 0;
81 }