题目描述:

新入职华为的小伙伴们都有在oj上面刷题的任务,共需要刷100道初级题,45道中级题,5道高级题,其中,做出来的高级题如果超标可以当初级或者中级题,做出来的中级题如果超标可以当初级题。每天,出题的大哥会给大家出Xi道题,这Xi道题属于同一个难度级别,小伙伴们要么用一天时间把这些题全做出来,要么就不做。现在,给你每天出题大哥出的题数以及难度,请问,小伙伴们最少要挑选其中几天去做题,才能把这150道题的任务完成呢?

输入示例:

5
100 70 5 5 55
1 2 2 2 3

输出:

 

表示两天就可以完成。

自己的解决思路:

这个题目的难点在于高难度的题目可以当做低难度的题目。
现将所有的题目按难度进行分类,并对每一类进行从大到小的排序。
首先,先做难度3的题目,如果难度三的题目搞定了 ,再将剩下的难度二和难度三的题目进行排序。在此基础上,再做难度二的。做完难度二以后,再将剩下的所有题目进行排序。在此基础上再做难度一的题目。
 
实现代码:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define LOWLEVEL 100
#define MIDLEVEL 45
#define UPLEVEL 5
bool MoreThan(int a,int b)
{
return a > b;
}
int theMax(int a,int b,int c)
{
return (a>b?(a>c?a:c):(b>c?b:c));
}
void display(char* str,vector<int> &src)
{
int i,n;
n = src.size();
cout<<str<<" : ";
for (i = 0; i < n; i++)
{
cout<<src[i]<<" ";
}
cout<<endl;
}
void OJDoWorks(int days,vector<int> &numbers,vector<int> &nandu)
{
int i,n;
int dayOver,flagu,flagm,flagl;
int lowsum,midsum,upsum;
vector<int> lowv, midv, upv,sortv,sortlv;
n = numbers.size();
flagl = flagm = flagu = -1;
lowsum = midsum = upsum = dayOver = 0;
//将题目进行分类
for (i = 0; i < n; i++)
{
if (nandu[i] == 1)
{
lowv.push_back(numbers[i]);
}
else if (nandu[i] == 2)
{
midv.push_back(numbers[i]);
}
else
{
upv.push_back(numbers[i]);
}
}
//按大小进行排序
sort(upv.begin(),upv.end(),MoreThan);
sort(midv.begin(),midv.end(),MoreThan);
sort(lowv.begin(),lowv.end(),MoreThan); display("up",upv);
display("mid",midv);
display("low",lowv);
n = theMax(upv.size(),midv.size(),lowv.size()); //先把高级的做满
for(i = 0; i < upv.size();i++)
{
dayOver++;
upsum += upv[i];
if (upsum >= UPLEVEL)
{
flagu = i;
break;
}
}
//高级题目不够
if (flagu < 0)
{
return;
}
midsum = upsum - UPLEVEL;
//将剩下的高级和中级的题目进行排序
for (i = flagu+1; i< upv.size(); i++)
{
sortv.push_back(upv[i]);
}
for (i = 0; i < midv.size(); i++)
{
sortv.push_back(midv[i]);
}
sort(sortv.begin(),sortv.end(),MoreThan);
display("sort mid:",sortv);
//再把中级的做满
n = sortv.size();
for (i = 0; i < n; i++)
{
if (midsum >= MIDLEVEL)
{
flagm = i;
break;
}
dayOver++;
midsum += sortv[i];
}
//中级题目数量不够
if (flagm < 0)
{
return;
}
lowsum = midsum - MIDLEVEL;
//再做低级的题目
for ( i = flagm; i < n; i++)
{
sortlv.push_back(sortv[i]);
}
for (i = 0; i < lowv.size(); i++)
{
sortlv.push_back(lowv[i]);
}
sort(sortlv.begin(),sortlv.end(),MoreThan);
display("sort low",sortlv);
n = sortlv.size(); for (i = 0; i < n; i++)
{
if (lowsum >= LOWLEVEL)
{
flagl = i;
break;
}
dayOver++;
lowsum += sortlv[i];
}
if ((upsum >= UPLEVEL) && (midsum >= MIDLEVEL) && (lowsum >= LOWLEVEL))
{
cout<<dayOver<<endl;
}
else
{
return;
}
}
int main()
{
//fstream in("data.txt");
int n,i,value;
vector<int> numbers,nandu; cin>>n;
for (i = 0; i < n; i++)
{
cin>>value;
numbers.push_back(value);
}
for (i = 0; i < n; i++)
{
cin>>value;
nandu.push_back(value);
}
OJDoWorks(n,numbers,nandu); cout<<endl;
return 0;
}

  

最新文章

  1. 去除inline-block元素间间距
  2. 基于C/S架构的3D对战网络游戏C++框架 _【不定期更新通知】
  3. JCS缓存使用类
  4. js判断访问的当前设备是手机还是电脑
  5. replicate-rewrite-db
  6. Linux内核分析——第七周学习笔记20135308
  7. 【转】MYSQL入门学习之八:数据库及表的基本操作
  8. 【Todo】MQ学习-RabbitMQ, ActiveMQ, Kafka等
  9. 网络解析之XML及JSON
  10. Haskell高阶函数
  11. Android 自定义CheckBox样式
  12. javascript中0级DOM和2级DOM事件模型浅析
  13. 让浏览器非阻塞加载javascript的几种方式
  14. hdoj Scaena Felix
  15. Python with
  16. git知识总结-1.git基础之git分布式
  17. 解决Chrome 70及以上版本的证书问题:Failed to load resource: net::ERR_CERT_SYMANTEC_LEGACY
  18. 【C++】读取参数的类
  19. 用面向对象计算BMI指数
  20. Runtime、System、Object

热门文章

  1. Nginx反向代理关于端口的问题
  2. Python的平凡之路(7)
  3. lightoj1030
  4. hdu 2093
  5. 对hbase的学习
  6. 如何解决requireJs的模块加载超时
  7. HTML标签之&lt;q&gt; &lt;blockquote&gt;
  8. [URAL]刷题记录表
  9. Android 学习第5课,配置android
  10. js中Math.round、parseInt、Math.floor和Math.ceil小数取整总结