美团2022-3-5笔试

bool IsNear(int& n1, int& n2)
{
	return abs(n1 - n2) <= 1;
}

int main()
{
	int n;
	while ( cin >> n )
	{
		vector<int>numVec(n);
		for ( auto i = 0; i < n; ++i )
		{
			cin >> numVec[i];
		}
		sort(numVec.begin(), numVec.end());
		int sum = 0;
		int length = 1;
		for ( auto i = 1; i <= n; ++i )
		{
			if ( IsNear(numVec[i - 1], numVec[i]) )
			{
				length++;
			}
			else
			{
				if ( length % 2 == 1 )
					++length;
				sum += length / 2;
				length = 1;
			}
		}
		cout << sum << endl;
	}
	return 0;
}

int GetMaxLenth(set<int> disSet, int n)
{
	int maxx = 0;
	int last = 0;
	for ( auto i = disSet.begin(); i != disSet.end(); ++i )
	{
		if ( i == disSet.begin() )
		{
			maxx = *disSet.begin();
			last = *disSet.begin();
		}
		maxx = max(*i - last, maxx);
		last = *i;
	}
	maxx = max(n - last, maxx);
	return maxx;
}
int main()
{
	int n, m;
	while ( cin >> n >> m )
	{
		int xMax = n;
		int yMax = n;
		int zMax = n;
		vector<string> posVec;
		vector<int> disVec;
		set<int> disXVec;
		set<int> disYVec;
		set<int> disZVec;
		for ( auto i = 0; i < m; ++i )
		{
			string posStr;
			cin >> posStr;
			posVec.push_back(posStr);
		}
		for ( auto i = 0; i < m; ++i )
		{
			int dis;
			cin >> dis;
			disVec.push_back(dis);
		}
		for ( auto i = 0; i < m; ++i )
		{
			if ( posVec[i].compare("x") == 0 )
			{
				disXVec.insert(disVec[i]);
				xMax = GetMaxLenth(disXVec, n);
			}
			if ( posVec[i].compare("y") == 0 )
			{
				disYVec.insert(disVec[i]);
				yMax = GetMaxLenth(disYVec, n);
			}
			if ( posVec[i].compare("z") == 0 )
			{
				disZVec.insert(disVec[i]);
				zMax = GetMaxLenth(disZVec, n);
			}
			cout << xMax * yMax * zMax << endl;
		}
	}
}

bool firstIsHigh(vector<pair<int, int>>&writeMap, int k1, int k2)
{
	int k1P = 0;
	int k2P = 0;
	for ( auto i : writeMap )
	{
		if ( i.first == k1 )
			k1P = i.second;
		if ( i.first == k2 )
			k2P = i.second;
	}
	return k1 > k2;
}
int main()
{
	int n, m;
	while ( cin >> n >> m )
	{
		vector<int>numVec(n);
		vector<vector<int>>opVec;
		vector<pair<int, int>>readMap(n);
		vector<pair<int, int>>writeMap(n);
		for ( auto i = 0; i < n; ++i )
		{
			cin >> numVec[i];
		}
		int sum = 0;
		for ( auto i = 0; i < m; ++i )
		{
			vector<int>lines(4);
			cin >> lines[0];
			if ( lines[0] == 1 )
			{
				cin >> lines[1] >> lines[2];
				for ( auto i = lines[1] - 1; i < lines[2]; ++i )
				{
					readMap[i].first = i;
					readMap[i].second++;
				}
			}
			else if ( lines[0] == 2 )
			{
				cin >> lines[1] >> lines[2] >> lines[3];
				for ( auto i = lines[1] - 1; i < lines[2]; ++i )
				{
					writeMap[i].first = i;
					writeMap[i].second++;
				}
			}
			opVec.push_back(lines);
		}
		sort(readMap.begin(), readMap.end(), [](pair<int, int>a, pair<int, int>b)->bool{return a.second > b.second; });
		sort(numVec.begin(), numVec.end(), greater<int>());
		vector<int>newVec(n);
		for ( auto i = 0; i < n; ++i )
		{
			if ( readMap[i].second > readMap[i + 1].second && i != n - 1 )
			{
				newVec[readMap[i].first] = numVec[i];
			}
			else if ( readMap[i].second == readMap[i + 1].second && i != n - 1 )
			{
				if ( firstIsHigh(writeMap, readMap[i].first, readMap[i].second) )
				{
					newVec[readMap[i].first] = numVec[i];
				}
				else
				{
					newVec[readMap[i + 1].first] = numVec[i];
					newVec[readMap[i].first] = numVec[i + 1];
					++i;
					if ( i + 1 == n )
					{
						break;
					}
				}
			}
			if ( i == n - 1 )
			{
				newVec[readMap[i].first] = numVec[i];
			}
		}
		for ( auto op : opVec )
		{
			if ( op[0] == 1 )
			{
				for ( auto i = op[1] - 1; i < op[2]; ++i )
					sum += newVec[i];
			}
			else if ( op[0] == 2 )
			{
				for ( auto i = op[1] - 1; i < op[2]; ++i )
					newVec[i] += op[3];
			}
		}
		cout << sum << endl;
	}
	return 0;
}