首页 > 美团笔试 8.22 技术综合-后台方向 C++
头像
NaruseShiroha1
编辑于 2020-08-22 18:15
+ 关注

美团笔试 8.22 技术综合-后台方向 C++

第一题  100% 没什么好说的
但是不知道为什么一开始getline无法ac,改成cin就过了
#include<bits/stdc++.h>
using namespace std;

int T,K;
bool f;
string s;

int main()
{
	cin >> T;
	getchar();
	while (T --) {
		cin >> s;
//		getline(cin, s);
		f = true;
		K = 0;
		if (!s.size()) f = false;
		else if (!((s[0]>='a' && s[0]<='z') || (s[0]>='A' && s[0]<='Z'))) f = false;
		else {
			for (int i = 1 ; i < s.size() ; i ++) 
				if (s[i] >= '0' && s[i] <= '9') K ++;
				else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) ;
				else f = false;
		}
//		cout << s << " ";
		if (f && K) cout << "Accept\n";
		else cout << "Wrong\n";
	}
} 

第二题 100%
两次sort
#include<bits/stdc++.h>
using namespace std;

struct ss{
	int val, index;
	friend bool operator < (const ss& x, const ss& y) {
		if (x.val == y.val) return x.index < y.index;
		else return x.val > y.val;
	}
//	ss(int v, int k): val(v), index(v) {}
};

int N,M,A,B;
ss s[50005];
int ans[50005];

int main()
{
	cin >> N >> M;
	for (int i = 0 ; i < N ; i ++) {
		cin >> A >> B;
		s[i].val = A + 2*B;
		s[i].index = i+1;
	}
	sort(s, s+N);
	for (int i = 0 ; i < M ; i ++) {
//		cout << s[i].index << " " << s[i].val << "\n";
		ans[i] = s[i].index;
	}
	sort(ans, ans+M);
	for (int i = 0 ; i < M ; i ++)
		if (i == 0) cout << ans[i];
		else cout << " " << ans[i];
}

/**

5 2
5 10
8 9
1 4
7 9
6 10

5 3
1 10
1 1
1 11
1 10
6 10

**/

第三题 100%
维护一个前缀和用来求区间Value
然后用优先队列维护整个堆的情况
用Set(红黑树)+ Lower_bound(二分)来进行查找
#include<bits/stdc++.h>
using namespace std;

struct ss{
	int pre, bac, val;
	friend bool operator < (const ss& x, const ss& y) {
		return x.val < y.val;
	}
};

int N, M;
int a[50005], suf[50005];
priority_queue<ss> q;
set<int> s;
set<int>::iterator it;

int main()
{
	scanf("%d", &N);
	for (int i = 1 ; i <= N ; i ++) {
		scanf("%d", &a[i]);
		suf[i] = suf[i-1] + a[i];
	}
	ss temp;
	temp.pre = 1, temp.bac = N, temp.val = suf[N];
	q.push(temp);
	for (int i = 1 ; i <= N ; i ++) {
		scanf("%d", &M);
		s.insert(M);
		while (1 && q.size()) {
			temp = q.top();
			it = s.lower_bound(temp.pre);
			if (it == s.end()) break;
			if (*it > temp.bac) break;
			if (temp.bac == temp.pre) q.pop();
			else if (*it==temp.bac) {
				q.pop();
				temp.bac --;
				temp.val = suf[temp.bac] - suf[temp.pre-1];
				q.push(temp);
			} else if (*it==temp.pre) {
				q.pop();
				temp.pre ++;
				temp.val = suf[temp.bac] - suf[temp.pre-1];
				q.push(temp);
			} else {
				q.pop();
				ss a = temp, b = temp;
				a.bac = *it-1;
				a.val = suf[a.bac] - suf[a.pre-1];
				b.pre = *it+1;
				b.val = suf[b.bac] - suf[b.pre-1];
				q.push(a);
				q.push(b);
			}
		}
		if (q.size()) printf("%d\n", q.top().val);
		else printf("0\n");
	}
}


第四题 18%
暴力骗点分
#include<bits/stdc++.h>
using namespace std;

struct ss{
	int val;
	vector<int> e;	
};

int N,K,q,w;
int vis[2005];
ss a[2005];
//set<vector<int>> s;
set<set<int>> s;

void dfs(int index, set<int> now, int MAX, int MIN)
{
	if (MAX-MIN > K) return ;
	s.insert(now);
	for (int i = 0 ; i < a[index].e.size() ; i ++) {
		int x = a[index].e[i];
		if (vis[x]) ;
		else {
			vis[x] = 1;
//			now.push_back(x);
			now.insert(x);
			dfs(x, now, max(MAX, a[x].val), min(MIN, a[x].val));
			now.insert(x);
			vis[x] = 0;
		}
	}
}

int main()
{
	cin >> N >> K;
	for (int i = 1 ; i < N ; i ++) {
		cin >> q >> w;
		a[q].e.push_back(w);
		a[w].e.push_back(q);
	}
	for (int i = 1 ; i <= N ; i ++) cin >> a[i].val;
	
	
	for (int i = 1 ; i <= N ; i ++) {
		vis[i] = 1;
//		vector<int> temp;
//		temp.push_back(i);
		set<int> temp;
		temp.insert(i);
		dfs(i, temp, a[i].val, a[i].val);
		vis[i] = 0;
	}
	
//	for (auto i: s) {
//		for (auto j: i) cout << j << " ";
//		cout << "\n";
//	}
		
	
	cout << s.size();
}

第五题 100%
已知A和B,求MAX( SUM_A/A + SUM_B/B )
通分,易得求最大值的方法就是sort之后,把较大的值给AB中较大的那个
然后要求字典序最小,所以分类讨论一下
#include<bits/stdc++.h>
using namespace std;

struct ss{
	int val, index;
};

bool cmpA(ss x, ss y)
{
	if (x.val == y.val) return x.index > y.index;
	return x.val > y.val;
}

bool cmpB(ss x, ss y)
{
	if (x.val == y.val) return x.index < y.index;
	return x.val > y.val;
}

long long a, b;
long long s[40005];
ss m[40005];
char ans[40005]; 

int main()
{
	scanf("%lld%lld", &a, &b);
	for (int i = 1 ; i <= a+b ; i ++) {
		scanf("%lld", &s[i]);
		m[i].index = i;
		m[i].val = s[i];
	}
	
	if (a == b) {
		for (int i = 1 ; i <= a ; i ++) printf("A");
		for (int i = 1 ; i <= b ; i ++) printf("B");
		exit(0);
	}
	
	if (a < b) {
		sort(m+1, m+a+b+1, cmpB);
		for (int i = 1 ; i <= a ; i ++) ans[m[i].index] = 'A';
		for (int i = a+1 ; i <= a+b ; i ++) ans[m[i].index] = 'B';
		for (int i = 1 ; i <= a+b ; i ++) printf("%c", ans[i]);
		exit(0);
	}
	
	sort(m+1, m+a+b+1, cmpA);
	for (int i = 1 ; i <= b ; i ++) ans[m[i].index] = 'B';
	for (int i = b+1 ; i <= a+b ; i ++) ans[m[i].index] = ',A';
	for (int i = 1 ; i <= a+b ; i ++) printf("%c", ans[i]);
	
}

/**
2 3
1 4 4 4 7
**/







全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐