今日练习

今日练习记录

练习题目,UVA11292,UVA11729.

UVA11292

此题应用贪心算法即可。

//
// Created by 21122 on 2022/5/10/0010.
//
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{   //注意这道题的输入格式

    int n, m;
    while(std::cin >> n >> m)
    {
        if(n == 0 && m == 0)
        {
            break;
        }
        int max_nums = 20005;
        int A[20005], B[20005];   //A for the length of Dragon head and B for the payment of knight.

        for(int i = 0; i < n; i++)
        {
            std::cin >> A[i];
        }

        for(int j = 0; j < m; j++)
        {
            std::cin >> B[j];
        }

        std::sort(A, A + n);
        std:: sort(B, B + m);

//    for(int i = 0; i < n; i++)
//    {
//        cout << A[i] << endl;
//    }

        int total_counts = 0;
        if(n > m)
        {
            cout << "Loowater is doomed!" << endl;
            return 0;
        }

        else
        {
            int index_2 = 0;
            for(int index = 0; index < m; index++)
            {
                if(B[index] >= A[index_2])      //can
                {
                    total_counts += B[index];
                    index_2 ++;

                    if(index_2 == n)
                    {
                        break;                  //龙头砍完,跳出
                    }
                }
            }
            if(index_2 < n)                     //没砍完(
            {
                cout << "Loowater is doomed!" << endl;
            }
            else
            {
                cout << total_counts << endl;
            }
        }
    }
    return 0;
}

UVA11729

同样是贪心算法,但笔者私自认为混合了流水线计算时间的内容。(

可能是在计算时间方面的使用方法错误,导致代码跑超时了。

//
// Created by 21122 on 2022/5/11/0011.
//
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
using namespace std;

int main()
{
    int n;
    int index = 1;
    while(true)
    {
        std::cin >> n;
        if(n == 0)
        {
            break;
        }
        cout << "n is:" << n << endl;
        vector<vector<int>> v;
        int B, J;
        for(int i = 0; i < n; i++)
        {
            std::cin >> B >> J;             // B 是交代任务的时间、 J是执行任务的时间
            v.push_back(vector<int>{J, B});
//        vector<int> temp;
//        temp.push_back(B);
//        temp.push_back(J);
//        v.push_back(temp);

        }
        std::sort(v.begin(), v.end(), greater<vector<int>>());
        vector<vector<int>>::iterator iter;

//    for(iter = v.begin(); iter != v.end(); iter++)
//    {   //循环遍历(迭代法
//        for(int i = 0; i < v[0].size(); i ++)
//        {       //或 i < (*iter).size()
//            cout << (*iter)[i];
//        }
//        cout << endl;
//    }
//
//        for(int i = 0; i < v.size(); i++)
//        {   //下标遍历
//            for(int j = 0; j < v[0].size(); j++)
//            {
//                cout<<v[i][j] << " ";
//            }
//            cout << endl;
//        }

        int total_time = 0;
        int work_time = 0;
        int temp = 0;
        for(int i = 0; i < v.size(); i++)
        {
            int time_of_doing = v[i][0];
            int time_of_telling = v[i][1];

            //work_time += time_of_doing - temp ? work_time > 0 : 0;
            //if(temp >= )

            //(*iter)[1] = ((time_of_doing - temp) <= 0)? 0 : (*iter)[1] - temp;

            total_time += time_of_telling;

            for(int j = 0; j <= i; j ++)
            {   //对执行任务的时间进行处理
                //int sum = std::accumulate(i + 1, v.size(), 0);

                int sum = 0;
                for(int t = j + 1; t < v.size(); t ++)
                {
                    sum += v[t][0];
                }
                //cout <<"sum is:" << sum << endl;
                v[j][0] -= sum;
                if (v[j][0] <= 0)
                {
                    v[j][0] = 0;
                }

            }

            //temp = time_of_telling;
        }

        int adding = 0;
        for(iter = v.begin(); iter != v.end(); iter++)
        {
//        for(int i = 0; i < v[0].size(); i ++)
//        {       //或 i < (*iter).size()
//            cout << (*iter)[i];
//        }
//        cout << endl;
            adding = max(0, (*iter)[0]);
        }

        //int adding = max_element([1, 2, 3, 4, 5]);
        //cout << "total_time is:" << total_time + adding<< endl;
        std::cout <<"Case " << index <<": " << total_time + adding << endl;
        index += 1;

//        for(int i = 0; i < v.size(); i++)
//        {   //下标遍历
//            for(int j = 0; j < v[0].size(); j++)
//            {
//                cout<<v[i][j] << " ";
//            }
//            cout << endl;
//        }
    }
    return 0;
}

总结

第二道题超时,由于现在是02点16分,所以暂时先不改了。(

主要预习了C++中 vector 的使用,包括vector 的创建,遍历,vector 的 vector,sort 函数的使用,迭代器 iterator 的简单使用。