1. Money Change

In this problem, you will design and implement an elementary greedy algorithm used by cashiers all over the world millions of times per day.

1.1 Problem Description

Task: The goal in this problem is to find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.

Input Format: The input consists of a single integer $m$.

Constrains: $0<m < 10^3 $.

Output Format: Output the minimum number of coins with denominations 1, 5, 10 that changes $m$.

Sample 1

Input :

2

output:

2

$2 = 1 + 1$

Sample 2

Input :

28

output:

6

$28 = 10 + 10 + 5 + 1 + 1 + 1$

解题思路:使用贪心算法思想,先使用大的金额来换取零钱。可以证明这种做法是save move.

1.2 代码实现

#include <iostream>
using namespace std;
int get_change(int m) {
    int n = 0;
    int leave_m = m;
    if(leave_m >= 10) {
        n += (leave_m / 10);
        leave_m = leave_m % 10;
    }
    while(leave_m >= 5) {
        n += leave_m / 5;
        leave_m = leave_m % 5;
    }
    n += leave_m;
    return n;
}

int main() {
    int m ;
    cin >> m;
    cout << get_change(m) << endl;
}

2. Fractional knapsack

2.1 Problem Description

Task: The goal of this code problem is to implement an algorithm for the fractional knapsack problem.

Input Format: The first line of the input contains the number $n$ of items and the capacity $W$ of a knapsack. The next $n$ lines define the values and weights of items. The $i$-th line contains integers $v_i$ and $w_i$ -the value and the weight of $i$-th item, respectively.

Constrains: $ 1 \leq n \leq 10^3, 0\leq W \leq 2 \cdot 10^6; 0\leq v_i \leq 2 \cdot 10^6; 0\leq w_i \leq 2 \cdot 10^6$ for all $1\leq i \leq n$. All the numbers are integers.

Output Format: Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most $10^{-3}$. To ensure this, output your answer with at least four digits after the decimal point (otherwise your answer, while being computed correctly, can turn out to be wrong because of rounding issues).

Sample 1

Input :

3 50
60 20
100 50
120 30

output:

180.0000

Sample 2

Input :

1 10
500 30

output:

166.6667

解题思路:对于可分背包问题,我们首先将物体的单位重量的价值从大到小排序,接着先放入单位重量价值最多的物品。可以证明这种做法是save move.

2.2 代码实现

#include <iostream>
#include <vector>

using std::vector;
double get_optimal_value(int capacity, vector<int> weights, vector<int> values) {
    if (capacity == 0) {
        return 0;
    }
    double max_value_per_weight = 0.;
    double value_per_weight = 0.;
    int max_index = 0;
    // 选出单位重量价值最多的物品
    for (int i = 0; i < weights.size(); i++) {
        value_per_weight = (double)values[i]/(double)weights[i];
        if (value_per_weight > max_value_per_weight) {
            max_value_per_weight = value_per_weight;
            max_index = i;
        }
    }
    double value = 0.0;
    //如果该物品能完全放入,进入下一次递归。
    if (capacity >= weights[max_index]) {
        capacity = capacity - weights[max_index];
        value = value + values[max_index];
        weights.erase(weights.begin() + max_index);
        values.erase(values.begin() + max_index);

        return value + get_optimal_value(capacity, weights, values);
    }
    //如果不能,终止递归。
    else{
        value = value + capacity * max_value_per_weight;
    }
    return value;

}

int main() {
    unsigned int n, capacity;
    std::cin >> n >> capacity;
    vector<int> values(n);
    vector<int> weights(n);
    for (int i = 0; i < n; i++) {
        std::cin >> values[i] >> weights[i];
    }
    double optimal_value = get_optimal_value(capacity, weights, values);

    std::cout.precision(10);
    std::cout << optimal_value << std::endl;
    return 0;
}

3. Car Fueling

3.1 Problem Description

You are going to travel to another city that is located $d$ miles away from your home city. Your can can travel at most $m$ miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances $stop_1,stop_2,…,stop_n$ from your home city. What is the minimum number of refills needed?

Input Format. The first line contains an integer $d$. The second line contains an integer $m$. The third line specifies an integer $n$. Finally, the last line contains integers $stop_1,stop_2,…,stop_n$.

Assuming that the distance between the cities is $d$ miles, a car can travel at most $m$ miles on a full tank, and there are gas stations at distances $stop_1,stop_2,…,stop_n$ along the way, output the minimum number of refills needed. Assume that the car starts with a full tank. If it is not possible to reach the destination, output $−1$.

Constraints. $1 ≤ d ≤ 105. 1 ≤ m ≤ 400. 1 ≤ n ≤ 300. 0 < stop_1 < stop_2 < ··· < stop_n < d.$

Sample 1

Input :

950
400
4
200 375 550 750

output:

2

Sample 2

Input :

10
3
4
1 2 5 9

output:

-1

解题思路:对于汽车加油问题,我们采用贪心思想,首先选取能到达最远的加油点。然后转化成子问题。可以证明这种做法是save move。

#include <iostream>
#include <vector>

using std::cin;
using std::endl;
using std::cout;
using std::vector;
using std::max;

int compute_min_refills(const int dist, const int tank, const vector<int>& stops) {
    int num_stops = 0;
    int dist_min = 10000;
    int dist_tmp = 0;
    unsigned int index_min = 0;
    // 如果tank >= dist, 终止递归
    if (tank >= dist) {
        return 0;
    }
    if (stops[0] > tank) {
        return -1;
    }
   
    for (size_t i = 1; i < stops.size(); i++) {
        if ((stops[i] - stops[i-1]) > tank) {
            return -1;
        }
    }
        num_stops ++;
    for (size_t i = 0; i < stops.size(); i++) {
        if(tank >= stops[i]) {
            dist_tmp = tank - stops[i];
            if(dist_tmp < dist_min) {
                dist_min = dist_tmp;
                index_min = i;
            }
        }
        else {
            continue;
        }
    }
    //选取最远的停车点
    int dist_updated = dist - stops[index_min];
    vector<int> stops_updated(stops.size() - index_min - 1);

    for (size_t i = index_min+1; i < stops.size(); i++) {
        stops_updated[i - index_min - 1] = stops[i] - stops[index_min];
    }
    // 递归
    return num_stops + compute_min_refills(dist_updated, tank, stops_updated);
}

int main() {
    int d = 0;
    cin >> d;
    int m = 0;
    cin >> m;
    int n = 0;
    cin >> n;

    vector<int> stops(n);
    for(size_t i = 0; i < n; ++i) {
        cin >> stops[i];
    }
    cout << compute_min_refills(d, m, stops) << endl;
    return 0;
}

4. Maximum Advertisement Revenue

4.1 Problem Description

You have $n$ ads to place on a popular Internet page. For each ad, you know how much is the advertiser willing to pay for one click on this ad. You have set up $n$ slots on your page and estimated the expected number of clicks per day for each slot. Now, your goal is to distribute the ads among the slots to maximize the total revenue.

Given two sequences $a_1,a_2,…,a_n$ ($a_i $is the profit per click of the i-th ad) and $b_1,b_2,…,b_n$ ($b_i$ is the average number of clicks per day of the i-th slot), we need to partition them into n pairs ($a_i,b_j$) such that the sum of their products is maximized.

Input Format. The first line contains an integer $n$, the second one contains a sequence of integers $a_1,a_2,…,a_n$ , the third one contains a sequence of integers$b_1,b_2,…,b_n$.

Constraints. $1 ≤ n ≤ 10^3; −10^5 ≤ a_i,b_i ≤ 10^5 \quad for \quad all \quad 1 ≤ i ≤ n.$

Output Format. Output the maximum value of $\sum_{i=1}^N a_i c_i$, where $c_1,c_2,…,c_n$ is a permutation of $b_1,b_2,…,b_n$.

Sample 1

Input :

3
1 3 -5
-2 4 1

output:

23

解题思路:我们首先将$a_i,b_i$排序,接着将两个数组按顺序相乘求和即可得到结果。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long max_dot_product(vector<int> a, vector<int> b) {
    std::sort(begin(a), end(a));
    std::sort(begin(b), end(b));
    long long result = 0;
    for (size_t i = 0; i < a.size(); i++) {
        result += ((long long) a[i]) * b[i];
    }
    return result;
}

int main() {
    size_t n;
    cin >> n;
    vector<int> a(n), b(n);

    for(size_t i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(size_t i = 0; i < n; i++) {
        cin >> b[i];
    }
    cout << max_dot_product(a, b) << endl;
}

5. Collecting Signatures

5.1 Problem Introduction

You are responsible for collecting signatures from all tenants of a certain building. For each tenant, you know a period of time when he or she is at home. You would like to collect all signatures by visiting the building as few times as possible. The mathematical model for this problem is the following. You are given a set of segments on a line and your goal is to mark as few points on a line as possible so that each segment contains at least one marked point.

5.2 Problem Description

Task. Given a set of n segments ${[a_0,b_0],[a_1,b_1],…,[a_{n−1},b_{n−1}]}$ with integer coordinates on a line, find the minimum number m of points such that each segment contains at least one point. That is, find a set of integers X of the minimum size such that for any segment $[a_i,b_i]$ there is a point x ∈ X such that $ai ≤ x ≤ bi$.

Input Format. The first line of the input contains the number n of segments. Each of the following n lines contains two integers $a_i $and $b_i$ (separated by a space) defining the coordinates of endpoints of the i-th segment.

Constraints. .

Output Format. Output the minimum number m of points on the first line and the integer coordinates of m points (separated by spaces) on the second line. You can output the points in any order. If there are many such sets of points, you can output any set. (It is not difficult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)

Sample 1

Input :

3
1 3
2 5
3 6

output:

1
3

Sample 2

Input :

4
4 7
1 3
2 5
5 6

output:

2
3 6

解题思路:我们首先将线段的末尾由小到大排序,接着将第一个线段的末尾作为输出点之一,判断和其他线段是否有交叉,如果没有交叉,则将没有交叉的下一个线段的末尾作为输出点之一,以此类推。

#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
struct Segment {
    int start, end;
};

bool SortFunction(Segment i, Segment j) {
    return (i.end < j.end);
}
vector<int> optimal_points(vector<Segment> &segments) {
    vector<int> points;
    std::sort(segments.begin(), segments.end(), SortFunction);
    int point = segments[0].end;
    points.push_back(point);
    for (size_t i = 1; i < segments.size(); i++) {
        if (point < segments[i].start || point > segments[i].end) {
            point = segments[i].end;
            points.push_back(point);
        }
    }
    return points;
}

int main() {
    int n;
    cin >> n;
    vector<Segment> segments(n);
    for(size_t i = 0; i < segments.size(); i++) {
        cin >> segments[i].start >> segments[i].end;
    }
    vector<int> points = optimal_points(segments);
    cout << points.size() << endl;
    for(size_t i = 0; i < points.size(); i++) {
        std::cout << points[i] << " ";
    }
}