牛牛找工作
题目
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
输入描述
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。
输出描述:
对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。
输入例子1:
3 3
1 100
10 1000
1000000000 1001
9 10 1000000000
输出例子1:
100
1000
1001
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class work {
public:
int di;
int pi;
work()
{
di = 0;
pi = 0;
}
};
class student {
public:
int ai;
int id;
student()
{
ai = 0;
id = 0;
}
};
bool sortByPi(const work &w1, const work &w2)
{
if (w1.di == w2.di)
{
return w1.pi > w2.pi;
}
else
{
return w1.di < w2.di;
}
}
bool sortByAi(const student &stu1, const student &stu2)
{
return stu1.ai < stu2.ai;
}
int main()
{
int n, m;
cin >> n >> m;
vector<work> vec_work(n);
vector<student> vec_student(m);
for (int i = 0; i < n; i++)
{
cin >> vec_work[i].di >> vec_work[i].pi;
}
sort(vec_work.begin(), vec_work.end(), sortByPi);
for (int j = 0; j < m; j++)
{
cin >> vec_student[j].ai;
vec_student[j].id = j;
}
sort(vec_student.begin(), vec_student.end(), sortByAi);
int worknum = 0, ans = 0;
int max_pi[101000];
for (int i = 0; i < m; i++)
{
while (worknum < n && vec_student[i].ai >= vec_work[worknum].di)
{
ans = max(vec_work[worknum].pi, ans);
worknum++;
}
max_pi[vec_student[i].id] = ans;
}
for (int i = 0; i < m; i++)
{
cout << max_pi[i] << endl;
}
return 0;
}
被3整除
题目：
Q得到一个神奇的数列: 1, 12, 123,…12345678910,1234567891011…。
并且小Q对于能否被3整除这个性质很感兴趣。
小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。
输入描述:
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。
输出描述:
输出一个整数, 表示区间内能被3整除的数字个数。
输入例子1:
2 5
输出例子1:
3
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
int l,r;
int cnt=0;
cin>>l>>r;
for(int i=l;i<=r;i++){
if(i%3!=1){
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
安置路灯
题目：
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.'表示, 不需要照亮的障碍物格子用’X’表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有’.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入描述:
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含’.‘和’X’。
输出描述:
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。
输入例子1:
2
3
.X.
11
…XX…XX
输出例子1:
1
3
代码
#include<iostream>
#include<string>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
int num=0;
for(int i=0;i<n;++i)
{
if(s[i]=='.')
{
++num;
i+=2;
}
}
cout<<num<<endl;
}
}
迷路的牛牛
题目
牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。
输出描述:
输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。
输入例子1:
3
LRR
输出例子1:
E
代码
#include<iostream>
using namespace std;
char status = 'N';
int main()
{
int num = 0;
cin>>num;
string s={0};
cin>>s;
char ch;
for(int i=0;i<num;i++)
{
ch = s[i];
switch(ch){
case 'L':
if(status == 'N') {status = 'W';break;}
if(status == 'W') {status = 'S';break;}
if(status == 'S') {status = 'E';break;}
if(status == 'E') {status = 'N';break;}
case 'R':
if(status == 'N') {status = 'E';break;}
if(status == 'E') {status = 'S';break;}
if(status == 'S') {status = 'W';break;}
if(status == 'W') {status = 'N';break;}
}
}
cout << status << endl;
return 0;
}
数对
题目
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。
代码
#include<iostream>
using namespace std;
int main()
{
long int n,k;
long int res=0;
cin>>n>>k;
int count=0;
if(k==0)
{
cout<<n*n<<endl;
return 0;
}
for(int y=k+1;y<=n;++y)
{
res+=n/y*(y-k);
if(n%y>=k)
{
res+=n%y-k+1;
}
}
cout<<res<<endl;
return 0;
}
矩形重叠
题目
平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <limits.h>
using namespace std;
// square overlap
class Square{
public:
int left, right, up, down;
bool operator <(const Square &x){
return down < x.down;
}
};
bool leftto(Square a, Square b){
return a.left < b.left;
}
void eraselower(vector<Square> &a, int ybound){
int deln = 0, i = 0, n = a.size();
while(i + deln < n){
if(a[i].up<=ybound)
swap(a[i], a[n-(++deln)]);
else
++i;
}
a.erase(a.end()-deln, a.end());
}
int main(){
int n;
cin>>n;
vector<Square> sqs(n), row;
for(int i=0; i<n; ++i)
cin>>sqs[i].left;
for(int i=0; i<n; ++i)
cin>>sqs[i].down;
for(int i=0; i<n; ++i)
cin>>sqs[i].right;
for(int i=0; i<n; ++i)
cin>>sqs[i].up;
sort(sqs.begin(), sqs.end());
int sn = 0, curdown = 0, res = 0;
while(sn<n)
{
curdown = sqs[sn].down;
while(sn<n && sqs[sn].down == curdown)
row.push_back(sqs[sn++]);
eraselower(row, curdown);
sort(row.begin(), row.end(), leftto);
vector<int> rights;
for(Square x:row)
{
rights.erase(rights.begin(), upper_bound(rights.begin(), rights.end(), x.left));
rights.insert(upper_bound(rights.begin(), rights.end(), x.right), x.right);
if(res < rights.size()) res = rights.size();
}
}
cout<<res<<endl;
}
牛牛的闹钟
题目
牛牛总是睡过头，所以他定了很多闹钟，只有在闹钟响的时候他才会醒过来并且决定起不起床。从他起床算起他需要X分钟到达教室，上课时间为当天的A时B分，请问他最晚可以什么时间起床
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示闹钟的数量N(N<=100)。
接下来的N行每行包含两个整数，表示这个闹钟响起的时间为Hi(0<=A<24)时Mi(0<=B<60)分。
接下来的一行包含一个整数，表示从起床算起他需要X(0<=X<=100)分钟到达教室。
接下来的一行包含两个整数，表示上课时间为A(0<=A<24)时B(0<=B<60)分。
数据保证至少有一个闹钟可以让牛牛及时到达教室。
输出描述:
输出两个整数表示牛牛最晚起床时间。
输入例子1:
3
5 0
6 0
7 0
59
6 59
输出例子1:
6 0
代码
#include<iostream>
using namespace std;
int main()
{
int N;
cin>>N;
int get[N];
int hi,mi,x,goclass;
int res=0;
for(int i=0;i<N;++i)
{
cin>>hi>>mi;
get[i]=hi*60+mi;
}
cin>>x>>hi>>mi;
goclass = hi * 60 + mi;
for (int i = 0; i < N; i++)
{
if (get[i] + x <= goclass && get[i] > res)
res = get[i];
}
cout <<res/60<<' '<<res%60;
return 0;
}
牛牛的背包问题
题目
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
输入描述:
输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。
输出描述:
输出一个正整数, 表示牛牛一共有多少种零食放法。
输入例子1:
3 10
1 2 4
输出例子1:
8
例子说明1:
三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有222 = 8种情况。
代码
#include<iostream>
#include<algorithm>
using namespace std;
long long nums = 1;
void DFS(vector<long long>& array, int size , long long w, long long sum, int pos){
if(sum <= w)
{
nums++;
for(int i = pos + 1 ; i < size ; ++i)
{
DFS(array,size,w,sum+array[i],i);
}
}
}
int main()
{
int n;
long long w;
cin >>n >> w;
long long total = 0;
vector<long long > array(n,0);
for(int i = 0 ; i != n ; ++i)
{
cin >> array[i];
total += array[i];
}
if(total <= w)
{
nums = pow(2,n);
}
else
{
sort(array.begin(),array.end());
for(int i = 0 ; i != n ; ++i)
DFS(array, array.size(), w, array[i],i);
}
cout<<nums<<endl;
return 0;
}
京公网安备 11010502036488号