问题1 : 图的遍历

描述

给定n个城市，n-1条道路的无向连通图。城市从1到n编号，LeeLdler想跑完所有的城市。也就是说LeeLdler打算从1号节点出发，走遍所有的城市，因为如果城市之间的距离太长，LeeLdler得跑死。所有令每条路的长度为1。但LeeLdler还是觉得自己会跑死，因此要你计算LeeLdler从一号城市开始经过所有城市的最短路程是多少。

 

输入格式

第一行包含一个整数N，1≤N≤10^5。

接下来N-1行，每行包含两个整数X和Y，表示X号城市和Y号城市之间有一条边，1≤X，Y≤N。

 

输出格式

输出总路程的最小值。

 

样例

样例输入 Copy

4
1 2
1 3
3 4

样例输出 Copy

4

 

思路： 
图的遍历，若想总路程最小，将最大深度的路径放在最后遍历 
除去最大深度的路径，其余边均需要遍历两遍（因为要遍历所有的点），所以 
最短路径 = 2 * (n-maxDeepth-1) + maxDeepth

例如：样例为

4
1 2
1 3
3 4

遍历过程为：1——2——1——3——4，总遍历次数为4 

 

AC代码：

#include<bits/stdc++.h>

using namespace std;
int dep[100005];  //结点深度，默认为0

int main()
{
    int n;
    cin >> n;
    int a,b;
    for(int i = 1; i < n; i++) {
        cin >> a >> b;
        dep[b] = dep[a] + 1;    //当前结点b的深度为前一个结点的深度+1
    }
    int maxDeepth = 0;   //存放最大深度
    for(int i = 1; i <= n; i++) {
        maxDeepth = maxDeepth < dep[i] ? dep[i] : maxDeepth;
    }
    
    //n-maxDeepth-1为其它结点，需遍历两遍，所以*2     maxDeepth最大深度，最后遍历    
    cout << 2 * (n-maxDeepth-1) + maxDeepth << endl;
    return 0;
}

 

 

问题 2: 外卖满减

描述

大家都点过外卖，外卖平台为了让大家多点些外面，总是会推出满减套餐。真香，哈哈哈。 现在，小嵇找到了一家外卖店，这个店是推出的满减套餐是满x元减10元。小嵇打算凑齐满减。 可是她又不想花费太多钱，故请你帮帮她，最少需要使用多少钱，才能凑到满减套餐。 注意：同一种食物，小嵇最多点一次，因为她不喜欢吃太多一样的。 

 

输入格式

第一行两个正整数n和X，分别表示菜品数量和券的最低使用价格。（1≤n≤100, 1≤X≤10000） 
接下来一行n个整数，第i个整数表示第i种菜品的价格。（1≤A_i≤100）

 

输出格式

一个数，表示最少需要选择多少元的菜才能使用满X元减10元，保证有解。

 

样例

样例输入 Copy

5 20
18 19 17 6 7

样例输出 Copy

23

思路：动态规划解法

定义状态dp[i][j] 表示购买前  i  个物品，超过金额  j  的最小金额数

推导出状态转移方程如下:

if(j <= a[i])
      dp[i][j] = min(a[i],dp[i-1][j]);
else
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);

 

AC代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 10010;
int dp[105][N];

int main()
{
    int n,x,a[105];

    while(~scanf("%d%d",&n,&x)) {
        for (int i = 1; i <= n; i++)
        cin >> a[i];

        for (int i = 0; i <= x; i++)
            dp[0][i] = N;

        for (int i = 1; i <= n; i++) {
            for(int j = 0; j <= x; j++) {
                if(j <= a[i])
                    dp[i][j] = min(a[i],dp[i-1][j]);
                else
                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
            }

        }
        cout << dp[n][x] << endl;
    }
    return 0;
}

 

每日一言：

 最可悲的是——

           你一生口号响确碌碌无为，还安慰自己可贵

           一生寂寂无名，还安慰自己与世无争