NOIP C++编程实战案例

NOIP（全国青少年信息学奥林匹克竞赛）是中国计算机学会主办的一项传统竞赛活动，旨在发现和培养青少年计算机编程人才。以下是一些C++编程实战案例，这些案例不仅展示了C++编程的实际应用，也反映了NOIP竞赛中可能遇到的题型和难度：

接水问题

• 问题描述：学校里有一个水房，有m个水龙头和n名同学，每个水龙头每秒钟供水量为1。同学们按照接水顺序接水，求所有同学接完水所需的总时间。
• 解题思路：使用贪心算法，每次让当前接水量最少的同学接水，直到所有同学都接完水。
• 代码示例：

#include
using namespace std;
int main(){
    int m, n;
    cin >> m >> n;
    if(n > m) n = m;
    int arr[10000];
    int flag = 0;
    for(int i = 1; i <= m; i++){
        cin >> arr[i];
        flag += arr[i];
    }
    int index = n + 1;
    int count = 0;
    while(flag != 0){
        for(int i = 1; i <= n; i++){
            if(arr[i] > 0){
                arr[i]--;
                flag--;
            }
            if(arr[i] == 0){
                arr[i] = arr[index];
                arr[index] = 0;
                if(index != m) index++;
            }
        }
        count++;
    }
    cout << count;
    return 0;
}

铺砖问题

• 问题描述：对于一个2行N列的走道，用12和22的砖去铺满，求有多少种不同的铺法。
• 解题思路：使用递归和动态规划的思想，通过记忆化搜索来减少重复计算。
• 代码示例：

#include
#include
using namespace std;
long long pave(int n){
    long long c[3] = {0};
    c[0] = 1;
    c[1] = 3;
    c[2] = 5;
    if(n == 1) return 1;
    else if(n == 2) return 3;
    else if(n == 3) return 5;
    else return pave(n - 1) + 2 * pave(n - 2);
}
int main(){
    int n;
    cout << "请输入走道的列数N" << endl;
    while(cin >> n){
        if(n == 0){
            cout << "输入有误，请重新输入！" << endl;
            continue;
        }
        cout << "对应的铺法有:" << endl;
        cout << pave(n) << endl;
        cout << "铺砖已完成" << endl;
        cout << "请输入下一走道的列数:（无其他输入请按EOF结束）" << endl;
    }
    return 0;
}

龙虎斗

• 问题描述：给定n个军营和m个工兵，每个军营有一定数量的工兵，求最少需要多少工兵才能将所有军营全部占领。
• 解题思路：使用动态规划的思想，通过构建一个二维数组来记录每个状态下的最小工兵数，最终得到结果。
• 代码示例：

#include
using namespace std;
long long n, c[1000010], m, p1, s1, s2;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    cin >> m >> p1 >> s1 >> s2;
    //p1军营加上s1个工兵c[p1] += s1;//原始气势
    long long sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++) {
        if (i < m) {
            //龙的气势
            sum1 += (m - i) * c[i];
        } else if (i > m) {
            //虎的气势
            sum2 += (i - m) * c[i];
        }
    }
    //判断s2加给谁比较好
    long long mmin = 1e19, index;
    for (int i = 1; i <= n; i++) {
        long long total1 = sum1, total2 = sum2;
        //加给龙虎其中一方
        if (i < m) {
            total1 += (m - i) * s2;
        } else if (m < i) {
            total2 += (i - m) * s2;
        }
        //计算气势差
        long long res = total1 > total2 ? total1 - total2 : total2 - total1;
        //记录最小的气势差 和 被加工兵的兵营号
        if (mmin > res) {
            mmin = res;
            index = i;
        }
    }
    cout << index;
    return 0;
}

这些案例展示了C++编程在实际应用中的多样性和复杂性，同时也反映了NOIP竞赛对选手编程能力和算法设计能力的考察。通过解决这些问题，参赛者可以提高自己的编程技巧和算法设计能力。