[数据结构与算法]TKK Summer Training Camp Round #1

伞兵代码 不吝赐教

1582 消灭星星

题解：

如下

代码：

#include <iostream>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int a[100005];
		int n, m;
		cin >> n >> m;
		for (int i = 0; i < n; i++)cin >> a[i];
		int cnt = 1;
		for (int i = 0; i < n; i++) {
			if (a[i] == 1) {
				cnt++;
				for (int j=i; true; j++) {
					if (a[j] == 0)break;
					else if (a[j] == 1)a[j] = 0;
				}
			}
		}
		if (cnt > m)cout << "NO" << endl;
		else cout << "YES" << endl;
	}
}

1584 光照强度-2

题解：

先输入每个点的光照强度，注意是最大光照强度，不要直接赋值。
然后从左上角遍历和右下角遍历 把值铺开。

#include<iostream>
using namespace std;
int p[1005][1005];
int maxp(int x, int y) {
	return max(p[x][y], max(max(max(p[x - 1][y] - 1, p[x + 1][y] - 1), p[x][y - 1]-1), p[x][y + 1] - 1));
}
int main()
{
	int a, b, m;
	cin >> a >> b >> m;
	while (m--) {
		int x, y, c;
		cin >> x >> y >> c;
		p[x][y] = max(p[x][y], c);
	}
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= b; j++) {
			p[i][j]=maxp(i, j);
		}
	}//左上
	for (int i = a; i > 0; i--) {
		for (int j = b; j > 0; j--) {
			p[i][j] = maxp(i, j);
		}
	}
	//右下
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= b; j++) {
			if (j == b)cout << p[i][j] << endl;
			else cout << p[i][j] << " ";
		}
	}
	return 0;
}

1585 下馆子-3

题解：

计算最终的最大出勤次数，并记录每一次操作完的name和当前的time。如果最大值是唯一的直接输出，否则遍历每一次操作完的name和time，找出最先大于等于最终最大出勤次数的time对应的name。

代码：

        
#include <iostream>
#include<map>
using namespace std;
typedef long long ll;
struct l{
	string name;
	int  time;
}arr[100005];
int main()
{
	int n;
	cin >> n;
	int t;
	map<string, int>m;
	for (int i = 0; i < n; i++) {
		string name;int time;
		cin >> name >> time;
		arr[i].name = name;
		map<string, int>::iterator pos = m.find(name);
		if (pos == m.end()) {
			m.insert(pair<string, int>(name, time));
			arr[i].time = time;
		}
		else {
			pos->second += time;
			arr[i].time = pos->second;
		}
	}
	int maxt = -50000001;
	for (auto x : m) {
		if (x.second > maxt)maxt = x.second;
	}
	int cnt = 0;
	string tname;
	for (auto it : m) {
		if (it.second == maxt)cnt++, tname = it.first;
		if (cnt > 1)break;
	}
	if (cnt == 1)cout << tname;
	else {
		for (int i = 0; i < n; i++) {
			if (arr[i].time >= maxt) {
				cout << arr[i].name;
				break;
			}
		}
	}
}