今日练习记录
练习题目,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 的简单使用。