算法编程题总结（一）

1.小美的送花线路

小美是美团的一名鲜花快递员鲜花是一种保质期非常短的商品所以需要尽快送到客户手中公司对于骑手的一个要求就是要规划送花的线路使得骑手送完所有订单走的路程尽可能少。(骑手开始派送时带走了所有需要派送的花不必每单后返回花店路程结算是从花店出发到送完最后一名客户为止不计算从最后一名客户家回到花店的时间)

公司对于骑手的绩效评价是取决于两个指标一是从花店到所有客户地址的距离之和另一个是骑手实际走的路程。

设花店始终位于1号位置客户共有n-1个其编号为2~n。令dis(i,j)表示i号位置到j号位置的距离即分别计算\sum_{i=2}^{n}dis(1, i)∑i=2ndis(1,i), 和骑手实际所走的最短路程。

为了简化问题我们约束这n个位置构成的是一棵树即只有n-1条边在其中互相连接且保证n个点彼此连通。

时间限制C/C++ 1秒其他语言2秒

空间限制C/C++ 256M其他语言512M

输入描述

输出第一行包含一个正整数n即花店和客户的总数。(1<=n<=30000)

接下来有n-1行每行有三个整数u,v,w表示在u和v之间存在一条距离为w的道路。(1<=w<=1000)

输出描述

输出包含两个整数中间用空格隔开分别表示花店到所有客户地址的距离之和和骑手实际走的路程。

示例1

输入例子

5

1 2 3

1 3 1

1 4 2

2 5 1

输出例子

10 10

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Main{
    static int INF = 0x3f3f3f3f;
    static int N = (int)1e5 + 10;
    static int sum = 0, cnt = 0, maxPre = 0;
    public static void main(String[] args) throws Exception {
        int[] a1 = readLine();
        int n = a1[0];

        //建图
        ArrayList<ArrayList<int[]>> g = new ArrayList(n + 1);
        for(int i = 0; i < n + 1; i++) g.add(new ArrayList());
        for(int i = 0; i < n - 1; i++) {
            int[] a = readLine();
            g.get(a[0]).add(new int[]{a[1], a[2]});
        }

        dfs(0, 1, g);
        System.out.println(sum + " " +((cnt - maxPre) * 2 + maxPre));
    }

    //dfs计算根节点到我目前这个节点的距离
    static void dfs(int pre, int x, ArrayList<ArrayList<int[]>> g) {
        sum += pre;
        if(g.get(x).size() == 0) {
            maxPre = Math.max(maxPre, pre);
        }
        for(int[] i: g.get(x)) {
            cnt += i[1];
            dfs(pre + i[1], i[0], g);
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // 读取一行的数据保存为int数组
    static int[] readLine() throws Exception{
        String s = br.readLine();
        String[] strs = s.split(" ");
        int[] res = new int[strs.length];
        for(int i = 0; i < strs.length; i ++ ){
            res[i] = Integer.parseInt(strs[i]);
        }
        return res;
    }
}

2.小美的评分计算器

美团对于商家的评价体系是1-5星评价体系用户在完成订单之后可以对商家打1/2/3/4/5星而在客户端上商家的评级却不一定是整数而是会显示小数点后的一位。很显然这就需要一个计算器了小美拥有了一些商户的评价数据希望可以计算出商家在客户端上显示出的评分。

这个评分的计算非常简单就是对该商家的所有客户的星级评价做求一个平均然后去尾法显示小数点后的一位即可例如平均得分是3.55则显示的是3.5。例如某商家获得了1-5星评价各一个则显示的评分是(1+2+3+4+5)/5=3.0。

如果商家没有获得评价则显示0.0。

时间限制C/C++ 1秒其他语言2秒

空间限制C/C++ 256M其他语言512M

输入描述

输入包含5个整数依次分别表示商家获得1星到5星的评价数量每一种评价的数量都不大于1000。

输出描述

输出仅包含一个保留一位的小数表示商家在客户端上显示的评级。

示例1

输入例子

2 2 1 1 2

输出例子

2.8

import java.util.*;
import java.lang.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        float count = 0;//总人数
        float score = 0;//总分数


        for (int i = 0; i < 5; i++) {
            int num = sc.nextInt();
            count += num;
            score += num * (i + 1);
        }

        float x = score / count;
        String str = String.valueOf(x);
        int index = str.indexOf(".");
        str = str.substring(0, index + 2);
        System.out.println(str);
    }
}

3.小美的外卖节省钱计划

2020年的618不再仅仅是购物节啦同时也是美团外卖节小美早早就准备好了各种满减代金券为了最大程度的“省钱”当然是选择把这些代金券都用光啦

这些代金券都有一个使用门槛即满多少元的订单才可以使用。如果使用一个二元组<x,y>表示一张代金券即需要满x元才能优惠y元那么需要注意的是并不是所有代金券的x都是大于等于y的良心美团也会推出一些x<y的代金券。如果x<y,例如x=1y=2则购买1元商品的情况下无需付款不会退款给用户。

请问小美如果想用完这些代金券在保证总付款金额最小的情况下她最多购买多少钱的外卖呢

说明

1.一个订单只能用一张代金券。

2.同时满足总付款金额最少且购买的外卖价值最高例如两个优惠完都是1元的外卖一个原价3元另一个原价4元则选四元的。

3.由于美团商户很多所以对于任何一个价格我们都可以找到至少一种商品购买。

时间限制C/C++ 1秒其他语言2秒

空间限制C/C++ 256M其他语言512M

输入描述

输入第一行仅包含一个正整数n表示小美拥有的代金券数量。(1<=n<=50000)

接下来有n行每行有两个整数x和y表示一张代金券需要订单金额满x元可以使用能够优惠y元。(1<=x<=10000,1<=y<=10000)

输出描述

输出仅包含两个正整数中间用空格隔开,分别表示小美购买的外卖价值和她的实际付款金额。

示例1

输入例子

3

5 3

10 5

1 2

输出例子

17 7

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int value = 0, cost = 0;
        int x, y;
        for (int i = 0; i < n; i++) {
            String[] pair = br.readLine().trim().split(" ");
            x = Integer.parseInt(pair[0]);
            y = Integer.parseInt(pair[1]);
            if (x >= y) {
                value += x;
                cost += x - y;
            } else
                value += y;
        }
        System.out.println(String.format("%d %d", value, cost));
    }
}

4.小美的代金券要过期啦

外卖节即将过去了小美还有很代金券没有消费掉美团面向小美这样的用户推出了一个新的活动即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排小美可以进行任意多次如下操作

如果存在相邻的两个代金券金额相等,设其面额为x小美可以使用这两张代金券换一张面额为x+1的代金券并将其仍放在原来两张券的位置上每进行一次这样的操作小美就可以获得1元可以无限期使用的奖励金。

小美觉得奖励金可太香了因此她想获得尽可能多的奖励金请问她最多可以获得多少奖励金。

时间限制C/C++ 1秒其他语言2秒

空间限制C/C++ 256M其他语言512M

输入描述

输入第一行仅包含一个正整数n表示小美拥有的代金券数量。(1<=n<=500)

输入第二行包含n个正整数每个整数x表示一张代金券的面额同时这也是系统排出的代金券顺序。(1<=x<=100)

输出描述

输出仅包含一个整数表示小美最多可以获得的奖励金数量。

示例1

输入例子

5

1 1 1 1 1

输出例子

3

例子说明

{1,1,1,1,1}->{1,1,1,2}->{1,2,2}->{1,3}

#include<stdio.h>
int* fun(int num, int quan[]) {//排序
    int i, j;
    for (i = 0; i < num; i++)
        for (j = num - 1; j > 0; j--) {
            if (quan[num - 1] < quan[num - 2]) {
                int temp = quan[num - 1];
                quan[num - 1] = quan[num - 2];
                quan[num - 2] = temp;
            }
        }
    return quan;
}
int fun2(int num, int quan[]) {
    int i, j;
    int count = 0;
    int jishu;
    do {
        jishu = 0;
        for (i = 0; i < num - 1; i++)
            if (quan[i] == quan[i + 1] && quan[i] != 0) {
                jishu++;
                quan[i]++;
                i++;
                quan = fun(num, quan);
            }
        count += jishu;
    } while (jishu != 0);
    return count;
}
int main() {
    int num;
    int* r;
    scanf("%d", &num);
    int quan[num];
    for (int m = 0; m < num; m++)
        scanf("%d", &quan[m]);
    r = fun(num, quan);
    printf("%d", fun2(num, r));
}