拼多多0515 笔试第一第二题

1、多多的商品编号

多多君接到了一个给活动商品编号的任务:每次可选的商品编号区间是[L,R]。由于活动的日期定在05月20号，多多君认为包含5，20和520的编号是有特殊含义，准备保留给对应的商品。例如:618520,其中包含了520，是一个特殊编号;而12368就是一个普通编号。多多君想知道，在可选的商品编号区间内，有多少符合上面要求的特殊编号。

输入描述

第一行，1个整数T，表示每次可选的编码区间。( 1 <=T<= 1,000 ) 接下来T行，每行2个整数:L和R，表示编码可选的区间(闭区间，即包括L和R)。( 1<=L<=R<= 1,000,000 )

输出描述

共T行，每行3个整数，分别表示对应区间里的5、20和520的编号数量

输入

输出

2 1 0
252 19 1
1441 187 6

思路

前缀和：str.find("") ==string::npos

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
	

	int n = 0;
	cin >> n;
	vector<vector<int>> inter(n, vector<int>(2, 0));
	for (int i = 0; i < n; i++) {
		cin >> inter[i][0] >> inter[i][1];

	}
	const int max = 1000000;
	
	vector<int> pre5(max + 1); //pre[i]表示前[0,i]中包含5得个数
	vector<int> pre20(max + 1);
	vector<int> pre520(max + 1);
	for (int i = 1; i < max; i++) {
		string str = to_string(i);
		pre5[i] = pre5[i - 1] + (str.find("5")!= string::npos);
		pre20[i] = pre20[i - 1] + (str.find("20") != string::npos);
		pre520[i] = pre520[i - 1] + (str.find("520") != string::npos);
	}
	for (vector<int>& vec : inter) {
		cout << pre5[vec[1]] - pre5[vec[0] - 1] << " ";
		cout << pre20[vec[1]] - pre20[vec[0] - 1] << " ";
		cout << pre520[vec[1]] - pre520[vec[0] - 1] << " ";
		cout << endl;
	}
	system("pause");
	return 0;
}

2、多多的植树计划

思路：优先队列 + 转换思路：直接浇水(+a-b), 目标健康度(m =m- b)

多多君在多多农场的某块林地上种了N颗树苗（(编号1~N)，其中第i颗树有健康度Hi。多多君计划给树苗们浇水，每次给某棵树苗浇水可以使其健康度上升A点;同时由于水的流动，其他树苗的健康度都会上升B点(其中A大于等于B)。为了每棵树苗都能够顺利成长，多多君希望所有树苗的健康度都大于或等于M。多多君想知道，在达到这个目标的前提下，最少的浇水次数是多少。

输入描述

第一行，4个整数N，M，A和B，分别表示农场中树苗的数量、目标达到的健康度、直接浇水增加的健康度和间接浇水增加的健康度。( 1 <= N,M,A,B<= 1,000,000，A >=B) 接下来N行，每行1个整数Hi，分别表示第i棵树苗初始的健康度Hi。(0<= Hi <= 1,000,000 )

输出描述

共一行，1个整数，表示最少的浇水次数使得所有树苗都能达到目标的健康度。

输入

输入

说明

两次浇水:
第一次浇水选择第1号树苗，树苗们的健康度变为:{7，6，9,11}
第二次浇水选择第2号树苗，树苗们的健康度变为:{ 10,11，12,14 }
满足所有树苗的健康度都大于或等于10

示例2

输入

输出

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int main() {
	
	int n; //树苗数量
	int m; //目标健康度
	int a; //直接浇水增加的健康度
	int b; //间接浇水增加的健康度
	cin >> n >> m >> a >> b;
	vector<int> H(n); //树苗健康度
	for (int i = 0; i < n; i++) {
		cin >> H[i];
	}
	//优先队列
	priority_queue<int,vector<int>, greater<int>> pq;
	for (int& h : H) {
		pq.push(h);
	}
	int cnt = 0;
	while (m > pq.top()) {
		int t = pq.top() + a - b;
		pq.pop();
		pq.push(t);
		m = m - b;
		cnt++;
	}
	cout << cnt << endl;
	system("pause");
	return 0;
}