一、相关例题（贪心）

1.找零

题目描述
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？如果无法支付K元，则输出-1。
输入
输入第一行为一个整数T，表示样例个数。
对于每个样例，第一行输入一个整数N表示需要找零的钱数，第二行输入7个整数表示每个纸币拥有的数量，分别表示1,2,5,10,20,50,100纸币的个数。
输出
对于每个样例，输出一个数字表示最少找零个数，输出-1表示无法找开。
样例输入
2
107
1 1 1 1 1 1 1
200
1 1 1 1 1 0 0
样例输出
3
-1
提示
数据保证贪心可解。

题目分析
先输入找零的钱和每张纸币的个数（数组c），之后依次在循环内判断100，50，20，10，5，2，1这些面值：如果现在仍需找零的钱比现在遍历到的面值大而且有这个面值的钱——如果所有这个面值的钱加起来大于应该找零的钱，就使用r / rmb[i]张，并且更新r和cnt；否则就全部使用并且更新r和cnt，以此类推。最后如果r = 0就输出cnt，否则输出-1。（注意最外层循环）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int c[7], m, rmb[7] = {1, 2, 5, 10, 20, 50, 100};
        cin >> m;//输入需要找零的钱数
        for (int i = 0; i < 7; i++)
            cin >> c[i];//输入每张面值的钱的张数
        int r = m, cnt = 0;
        for (int i = 6; i >= 0; i--) {//遍历7次
            if (r / rmb[i] > 0 && c[i] > 0) {//如果r大于这个面值且有这个面值的钱
                if (c[i] >= r / rmb[i]) {//如果这个面值的钱的张数多于需要的最多张数
                    cnt += r / rmb[i];//cnt加上需要的最多张数
                    r = r % rmb[i];//更新r为r%这个面值（因为一定小于这个面值）
                }
                else {//如果这个面值的钱的张数小于等于需要的最多张数
                    r = r - c[i] * rmb[i];//更新r为r-所有这个面值的钱的总钱数
                    cnt += c[i];//cnt加上所有的这个面值的钱的张数
                }
            }
        }
        if (r == 0) cout << cnt << endl;//如果剩下的需要找零的钱是0，就输出cnt
        else cout << "-1" << endl;//如果没有成功找零就输出-1
    }
    return 0;
}

2.Rightmost Digit（分治）

题目描述
给定一个整数T，表示有T组数据，每组包含一个整数N(N≤1000000000)，求每组数据N的N次方的最后一个数字。
输入
第一行输入一个整数T，表示样例个数。
对于每个样例，输入一个整数N，含义如题所示。
输出
对于每个样例，输出N^N的个位数。
样例输入
2
3
4
样例输出
7
6
题目分析
求n的n次方，使用递归的思想，work（m，k / 2）% 10，因为k的值过大，所以需要转化，又因为求k的k次方，可以写成k的k / 2次方的平方，所以先求k的k / 2次方，并且注意到只需要求个位，所以对10取余，之后判断，如果k是偶数，代表就这样算就可以，但是当k是奇数的时候，需要再乘k——代表k的k次方等于k*k的（k - 1）/ 2次方的平方，最后输出这个个位数即可（注意外层循环）

#include <bits/stdc++.h>
using namespace std;
long long work(long long int m, long long int k)
{
    long long int s;
    if (k == 1) return m;//如果是一次方的话直接输出
s = work(m, k / 2) % 10;/*算m的k / 2次方所得的个位数（递归思想）直到最后变成work（m， 1）的时候一层一层return，最后得到m的k / 2次方*/
    if (k % 2 == 0) return (s * s % 10);//如果k是偶数，就返回s的平方的个位数
    else return (s * s * m % 10);//否则返回s的平方再乘m的个位数
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        cout << work (n, n) << endl;//调用函数实现n的n次方
    }
    return 0;
}

3.Monthly Expense（二分）

题目描述
给出n天中每天的花费，需要将这些天分成m组，每组包含连续的一或多天，若第i组的花费为Ki，求一种分组方法使得K=max{Ki}最小。
输入
输入数据第一行为两个正整数N和M，之后输入N个正整数，分别表示第i天的费用。输出包含一行，表示上面描述的K。
输出
对于每组数据，输出一个数表示最小的花费。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
提示
n <= 100.
题目分析
本题思路为二分，首先输入每一天的花费，把他们都加起来作为high，同时取最大的一天的花费为low，定义mid是二者的和除以二。判断mid和输出值之间的关系：当假设mid就是输出值时，如果得到的可以分的组数大于应该分的组数，代表mid值偏小，更新high，否则更新low，以此类推，知道最后high = low。（注意最外层循环）

#include <bits/stdc++.h>
using namespace std;
int m, k;
int a[100006];
bool find(int top) {//作用就是判断在最大值是top的情况下能不能得到≥要求的组数
    int num = 1, cur = 0;//如果能就代表top的值小于等于现在输入的值，否则就大于
    for (int i = 0; i < m; i++) {
        if (cur <= top) {//如果cur小于等于top
            cur += a[i];//cur加上现在遍历到的那天的花费
        }
        if (cur > top) {//如果cur大于top
            num++;//组数加一
            cur = a[i];//cur就等于现在遍历到的那一天的花费
        }
    }
    return(num <= k);//如果num小于组数就返回false，否则返回true
}
int main()
{
    while (cin >> m >> k) {
        int sum = 0, max = 0;
        for (int i = 0; i < m; i++) {
            cin >> a[i];//输入m天的花费
            sum += a[i];//更新sum，加上第i天的花费
            if (a[i] > max)    max = a[i];//如果第i天的花费比最大值大，更新最大值
        }
        int low = max, high = sum, mid;//定义下界是max，上界是sum，mid
        while (low != high) {//当上下界不相等的时候
            mid = (low + high) >> 1;//mid更新为上下界的和除以二（也就是二分）
            if (find(mid)) high = mid;//如果能得到，就减小high到mid
            else low = mid + 1;//否则就增加low到mid+1
        }//最后跳出循环的时候上下界相等
        cout << low << endl;//输出最后得到的数
    }
    return 0;
}

4.三角形个数

题目描述
小b有一个仅包含非负整数的数组a，她想知道有多少个三元组(i,j,k)，满足i<j<k且a[i],a[j],a[k]可能作为某个三角形的三条边的边长。

输入
第一行输入一个正整数n，表示数组a中元素个数；第二行n个非负整数，表示a中元素，以空格隔开；其中0＜n≤1000，a中任意元素a[i]满足0≤a[i]≤1000。
输出
输出一个数，表示满足题意的三元组个数

样例输入
4
2 2 3 4
样例输出
3
题目分析
形成三角形只需要满足两边之和大于第三边，两边之差小于第三边，但是为了简化运算，先对边长进行从小到大的排序，那么只需要比较前面两个元素的和是否大于后面的元素，前面的一个元素是否大于后面元素-前面的另一个元素

#include <bits/stdc++.h>
using namespace std;
int a[1001];//正确的定义数组方式
int main()
{
    int n, cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];//输入每条边的边长
    sort(a, a + n);//从小到大排序
    for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
    for (int k = j + 1; k < n; k++)//写三层循环是为了让每三个元素都可以随机组合
        if (a[i] + a[j] > a[k] && a[i] > a[k] - a[j] && a[j] > a[k] - a[i]) {
            cnt++;//如果满足两边之差小于第三边，两边之和大于第三边就能形成三角形
        }
    cout << cnt << endl;
    return 0;
}

5.Greed

题目描述
Jafar has n cans of cola. Each can is described by two integers: remaining volume of cola ai and can’s capacity bi (ai  ≤  bi).
Jafar has decided to pour all remaining cola into just 2 cans, determine if he can do this or not!
输入
The first line of the input contains one integer n (2 ≤ n ≤ 100 000) — number of cola cans.
The second line contains n space-separated integers a1, a2, …, an (0 ≤ ai ≤ 10^9) — volume of remaining cola in cans.
The third line contains n space-separated integers that b1, b2, …, bn (ai ≤ bi ≤ 10^9) — capacities of the cans.
输出
Print “YES” (without quotes) if it is possible to pour all remaining cola in 2 cans. Otherwise print “NO” (without quotes).
You can print each letter in any case (upper or lower).

样例输入
2
3 5
3 6
样例输出
YES
题目分析
本题只需要新建两个数组，分别代表每个罐子中可乐体积和每个罐子的容积，在for循环中依次输入，同时在输入每个罐子中可乐体积的同时计算可乐的总体积，之后使用for循环找出罐子容积最大和第二大的罐子，最后把这两个罐子的容积加在一起和可乐总体比较，如果sum小于总体积就代表不能装下，输出no；大于或者等于就代表能装下，输出yes。

#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005];
int main()
{
 int n, sum = 0, s;
 cin >> n;
 for (int i = 0; i < n; i++) {
     cin >> a[i];//输入第i个罐子中剩余的可乐
     sum += a[i];//计算多有可乐的体积
 }
 for (int i = 0; i < n; i++) {
     cin >> b[i];//输入第i个罐子的容积
 }
 int max1 = 0, max2 = 0;
 for (int i = 0; i < n; i++) {
     if (b[i] > max2) {
         max2 = max1;
         max1 = b[i];
     }//得到所有罐子中最大和第二大罐子的容积
 }
 s = max1 + max2;//s代表这两个最大的罐子的容积和
 if (s >= sum) {//如果最大的容积和比所有可乐的体积大，即能放下
     cout << "YES" << endl;//输出yes
 }
 else  cout << "NO" << endl;//否则，也就是装不下，输出no
return 0;
}

6.珠心算测验

题目描述
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？
最近老师出了一些测验题，请你帮忙求出答案。
输入
共两行，第一行包含一个整数nn，表示测试题中给出的正整数个数。 第二行有nn个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。
输出
一个整数，表示测验题答案。
样例输入
4
1 2 3 4
样例输出
2
提示
由1+2=3,1+3=41+2=3,1+3=4，故满足测试要求的答案为22。 注意，加数和被加数必须是集合中的两个不同的数。
n <= 1000，集合中所有的数字保证小于等于1e7.
题目分析
本题输入的数据是杂乱无章的，所以首先需要给他们进行排序，从小到大，那么只需要计算前面两个元素的和，之后再与后面的元素进行比较即可；如果相等，输出的结果就加一。

#include <bits/stdc++.h>
using namespace std;
int a[10000001];
int main()
{
    int n, cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];//输入集合中的每一个元素
    }
    sort(a, a + n);//把集合中的元素从小到大排序
    for (int i = 2; i < n; i++) {
        for (int j = 0; j < i - 1; j++) {
            for (int k = j + 1; k < i; k++) {
                if (a[i] == a[j] + a[k]) {//如果后面的元素等于前面某两个元素的和
                    cnt++;//代表多了一个等于集合中另外两个不同的数的数
                    goto skip;//跳出循环使得后面的元素后移1位
                }
            }
        }
        skip: ;
    }
    cout << cnt << endl;//输出结果
    return 0;
}

7.Long Number

题目描述

输入

输出
Print the maximum number you can get after applying the operation described in the statement no more than once.
样例输入 Copy
4
1337
1 2 5 4 6 6 3 1 9
样例输出
1557
题目分析
首先输入字符串（便于之后对每一位元素的替换），并且使用数组a把字符类型的元素转化为数字，之后设置数组b代表函数内的元素；加两层for循环，如果a[i]等于j而且a[i]<b[j]时代表可以替换并且实现替换，但是注意在完成替换之后需要break防止进行二次替换。最后输出即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, b[10], a[6];
    string ar;
    cin >> n >> ar;
    int nm = ar.length();//限定输出的长度
    for (int i = 0; i < 6; i++) {
        a[i] = ar[i] - '0';//把字符转化为数字
    }
    for (int i = 1; i < 10; i++)
        cin >> b[i];//输入f（1）到f（9）
    for (int i = 0; i < 6; i++) {
        for (int j = 1; j < 10; j++) {
            if (a[i] == j && a[i] < b[j]) {//如果ar中的某一位等于j且小于f（j）
                a[i] = b[j];//重新把f（j)赋值给ar[i]
                break;//结束内层循环
            }
        }
    }
    for (int i = 0; i < nm; i++)//输出所有元素即可
    cout << a[i];
    cout << endl;
    return 0;
}