练习1-2 两枚硬币

分数 25

作者陈越

单位浙江大学

伊娃喜欢收集全宇宙的硬币，包括火星币等等。一天她到了一家宇宙商店，这家商店可以接受任何星球的货币，但有一个条件，无论什么价格，都必须用 2 枚硬币一次付清，不能多也不能少。而她有多达 105 个硬币，于是求助于你。给定任一价格，请帮她找出可以付款的 2 枚硬币。

输入格式：

第 1 行给出 2 个正整数：n (≤105)为硬币枚数、m（≤103）为伊娃要付清的价格；第 2 行给出 n 枚硬币的面值，均为不超过 500 的正整数。同行数字间以空格分隔。

输出格式：

在一行中输出两枚硬币的面值 v1 和 v2 ，以 1 个空格分隔，满足条件 v1+v2=m，并且 v1≤v2。如果这样的解不唯一，输出 v1 最小的那个解。如果解不存在，则输出 No Solution。

输入样例 1：

8 15
1 2 8 7 2 4 11 15

输出样例 1：

4 11

输入样例 2：

7 14
1 8 7 2 4 11 15

输出样例 2：

No Solution

解析

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

int main() 
{
    int n , m;
    cin >> n >> m;
    
    setvbuf(stdin, NULL, _IOFBF, 16384);
    setvbuf(stdout, NULL, _IOFBF, 16384);
    vector<int> coins(n);
    for (int i = 0; i < n; i++)
    {
        cin >> coins[i];
    }
    sort(coins.begin(), coins.end());

    int left = 0;
    int right = n - 1;
    bool found = false;
    while (left < right)
    {
        int current_sum = coins[left] + coins[right];
        if (current_sum == m)
        {
            found = true;
            cout << coins[left] << " " << coins[right] << endl;
            break;
        }
        else if (current_sum < m)
        {
            left++;
        }
        else
        {
            right--;
        }

    }
    if (!found)
    {
        cout << "No Solution" << endl;
    }
    return 0;
}

注意

还是先排序然后用双指针

实验1-2 爆气球

分数 20

作者陈越

单位浙江大学

爆气球对孩子们来说是很好玩的游戏。假设有 n 只气球被布置在一条直线上，游戏的目标很简单，就是爆掉尽可能多的气球。但是这里我们加一条特殊的规则 —— 你只能跳一次。我们假设聪明的娃穿了件浑身带刺的衣服，跳到某个位置，躺平（如下图所示），这样气球只要碰到娃身体的任何部分都会立刻爆炸。那么你的任务就是告诉娃应该跳到哪里，才能一次爆掉最多的气球。

输入格式：

输入第一行有两个正整数：n（≤105）为一条线上布置的气球的数量；h（≤103）为孩子伸直双臂能达到的高度。第二行给出 n 个整数，每个对应一只气球在直线轴上的坐标。题目保证坐标按递增顺序给出，所有坐标值在 [−106,106] 区间内。

输出格式：

在一行中输出孩子跳跃的位置坐标，使得孩子跳到这个位置然后躺平能够爆掉身下最多的气球；随后输出能爆掉的气球的最大数量。如果这个坐标不唯一，输出最小的那个值。

一行中的数字间应有 1 个空格，行首尾不得有多余空格。

输入样例：

11 120
-120 -40 0 80 122 140 160 220 240 260 300

输出样例：

120 5

**注意：**跳到从 120 到140，或 240 到 260 之间的任何位置，都可以爆掉 5 只气球，所以 120 作为最小的坐标被输出。

解析

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    setvbuf(stdout, nullptr, _IOFBF, 16384); 
    setvbuf(stdin, nullptr, _IOFBF, 16384);
    int n , m;
    cin >> n >> m;
    vector <int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int sum = 0;
    int left = 0;
    int best = 0;
    for (int right = 0; right < n; right++)
    { 
        while (left < right && a[right] - a[left] > m)
        {
            left++;
        }
        int count = right - left + 1;
        int current_left = a[right] - m;

        if (count > sum)
        {
            sum = count;
            best = current_left;
        }
    }
    cout << best << " " << sum << endl;
    return 0;
}

注意

1.声明一个vector，要

vector <int> a(n)

这样，是一个数组样的

2.气球的坐标是按从小到大排好的，这是个关键！咱们可以用两个 “标记”（比如叫 i 和 j）来圈出一段气球，这段气球刚好能被长度为 h 的区间盖住。具体怎么做呢？

（1）先让 j 从左到右一个一个看气球（j 是区间的右边界对应的气球）。

（2）对于每个 j，调整 i 的位置，让 i 尽量靠左，但必须保证：j 位置的气球和 i 位置的气球之间的距离 ≤ h（这样 i 到 j 之间的所有气球才能被区间盖住）。

（3）这时候 i 到 j 之间的气球数量，就是当前区间能盖住的气球数。咱们记录下最多的数量，以及对应的最小 x（x 就是 j 位置的气球坐标减去 h，因为区间右边界是 j 的位置，左边界就是 x=j 的位置 - h）。

算法2-1 在顺序表 list 中查找元素 x

分数 10

作者陈越

单位浙江大学

请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，查找其在顺序表中的位置。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的不重复的整数，数字间以空格分隔；最后一行给出待查找的元素 x，也是 int 范围内的整数。

输出格式：

在一行中输出 x 在顺序表中的位置，即数组下标。如果没找到，则输出 -1。注意数组下标从 0 开始。

输入样例 1：

5
1 2 3 4 5
4

输出样例 1：

输入样例 2：

5
4 3 6 8 0
1

输出样例 2：

-1

解析

#include <iostream>
using namespace std;
#include <vector>

int main()
{
    int n, m;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cin >> m;
    bool found = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == m)
        {
            cout << i << endl;
            found = 1;
            break;
        }
    }
    if (found)
    {

    }
    else
    {
        cout << "-1" << endl;
    }
}

算法2-2 在顺序表 list 的第 i 个位置上插入元素 x

分数 15

作者陈越

单位浙江大学

请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，将其插入顺序表中指定的第 i 个位置。注意：i 代表位序，从 1 开始，不是数组下标。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出插入位置 i 和待插入的元素 x，均为 int 范围内的整数。

输出格式：

分以下几种情况输出：

如果顺序表中已经有 104 个元素了，则不能插入，在一行中输出句子 错误：表满不能插入。。
如果插入的位置不合法，则不能插入，在一行中输出句子 错误：插入位置不合法。。
无论是否插入成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。

输入样例 1：

5
1 2 3 4 5
3 8

输出样例 1：

1 2 8 3 4 5

输入样例 2：

5
4 3 6 8 0
0 1

输出样例 2：

错误：插入位置不合法。
4 3 6 8 0

解析

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int c, x;
    cin >> c >> x;

    if (n >= 10000) {
        cout << "错误：表满不能插入。" << endl;
    }
    // 判断插入位置合法性（1 ≤ c ≤ n+1）
    else if (c < 1 || c > n + 1) {
        cout << "错误：插入位置不合法。" << endl;
    }
    // 合法情况：执行插入
    else {
        a.resize(n + 1);  // 扩展容量到n+1
        // 将下标c-1及之后的元素后移1位
        for (int i = n - 1; i >= c - 1; --i) {
            a[i + 1] = a[i];
        }
        a[c - 1] = x;  // 插入元素到目标位置
        n++;  // 元素个数更新为n+1
    }
    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

注意

vector容器如果拓展了空间，要resize，例如：

vector<int> a(n);
···
a.resize(n + 1);

插入顺序表

1.判断插入位置合法性（1 ≤ c ≤ n+1）

2.插入完后要将n++

算法2-3 从顺序表 list 中删除第 i 个元素

分数 15

作者陈越

单位浙江大学

请编写程序，将 n 个整数存入顺序表，对任一指定的第 i 个位置，将这个位置上的元素从顺序表中删除。注意：i 代表位序，从 1 开始，不是数组下标。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出删除位序 i，为 int 范围内的整数。

输出格式：

如果删除的位置不合法，则不能删除，在一行中输出句子 错误：不存在这个元素。。无论是否删除成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。

输入样例 1：

5
1 2 3 4 5
3

输出样例 1：

1 2 4 5

输入样例 2：

5
4 3 6 8 0
0

输出样例 2：

错误：不存在这个元素。
4 3 6 8 0

解析

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int m;
    cin >> m;
    if (m < 1 || m > n)
    {
        cout << "错误：不存在这个元素。" << endl;
    }
    else
    {
        for (int i = m - 1; i < n - 1; i++)
        {
            a[i] = a[i + 1];
        }
        n--;
        a.resize(n);
    }
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

练习1-2 两枚硬币

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

解析

注意

实验1-2 爆气球

输入格式：

输出格式：

输入样例：

输出样例：

解析

注意

算法2-1 在顺序表 list 中查找元素 x

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

解析

算法2-2 在顺序表 list 的第 i 个位置上插入元素 x

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

解析

注意

vector容器如果拓展了空间，要resize，例如：

插入顺序表

算法2-3 从顺序表 list 中删除第 i 个元素

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

解析

注意

删除

结束