CF1182C 求助(题目里面发没人回复aaa)
  • 板块灌水区
  • 楼主E1_de5truct0r
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/1/22 15:16
  • 上次更新2023/11/5 04:33:43
查看原帖
CF1182C 求助(题目里面发没人回复aaa)
195198
E1_de5truct0r楼主2021/1/22 15:16
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct st
{
	int num,len,id; //num存元音个数,len存长度,id存顺序 
	char lst; //存最后一个元音是什么 
}a[100005];

inline bool cmp(st a,st b)
{
	if(a.num!=b.num) return a.num>b.num; //先按着元音个数排序 
	else return a.lst<=b.lst; //然后按着最后的元音字母大小顺序排 
}
char str[100005][105];
struct ans
{
	int a,b,c,d;
}b[100005];
bool book[100005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>str[i];
		//元音个数 ↓ 
		int len=strlen(str[i]);
		for(int j=0;j<len;j++)
		{
			if(str[i][j]=='a'||str[i][j]=='e'||str[i][j]=='i'||str[i][j]=='o'||str[i][j]=='u')
			{
				a[i].lst=str[i][j]; //更新最后的元音 
				a[i].num++; //元音个数++ 
			}
		}
		//长度等其他变量 ↓ 
		a[i].len=len;
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp); //排序,方便把相同的放到一起 
	
	queue<int> q1,q2; //q1存储能作为第一对的歌词,q2存储能作为第二个的歌词
	for(int i=1;i<=n;i++)
	{
		if(a[i].num==a[i+1].num && a[i].lst==a[i+1].lst)
		{
			q2.push(a[i].id);
			q2.push(a[i+1].id);
			book[i]=book[i+1]=true;
			i++;
		}
	}//挑能够做第二对歌词的 能做第二对歌词的一定能做第一对歌词
	
	for(int i=1;i<=n;i++)
	{
		int tmp1,tmp2;
		while(book[++i]);tmp1=i;
		while(book[++i]);tmp2=i;
		if(tmp1>n || tmp2>n) break;
		if(a[tmp1].num==a[tmp2].num)
		{
			q1.push(a[tmp1].id);
			q1.push(a[tmp2].id);
		}
	}
	int m=0;
	if(q2.size()<q1.size())
	{
		while(!q2.empty())
		{
			int fr1,fr2,ls1,ls2;
			fr1=q1.front();q1.pop();
			ls1=q2.front();q2.pop();
			if(q2.empty()) break;
			fr2=q1.front();q1.pop();
			ls2=q2.front();q2.pop();
			b[++m].a=fr1;
			b[m].b=ls1;
			b[m].c=fr2;
			b[m].d=ls2;
		}
		//能做第二对歌词的如果小于能做第一对歌词的,那么只能用所有的能做第二对歌词的来做 
	}
	else
	{
		while(!q1.empty())
		{
			int fr1,fr2,ls1,ls2;
			fr1=q1.front();q1.pop();
			ls1=q2.front();q2.pop();
			if(q1.empty()) break;
			fr2=q1.front();q1.pop();
			ls2=q2.front();q2.pop();
			b[++m].a=fr1;
			b[m].b=ls1;
			b[m].c=fr2;
			b[m].d=ls2;
		}
		while(!q2.empty())
		{
			int fr1,fr2,ls1,ls2;
			fr1=q2.front();q2.pop();
			if(q2.empty()) break;
			fr2=q2.front();q2.pop();
			if(q2.empty()) break;
			ls1=q2.front();q2.pop();
			if(q2.empty()) break;
			ls2=q2.front();q2.pop();
			b[++m].a=fr1;
			b[m].b=ls1;
			b[m].c=fr2;
			b[m].d=ls2;
		}
		//先用完第一对,再用第二对自己跟自己搭配 
	}
	std::cout<<m<<endl;
	for(int i=1;i<=m;i++)
		cout<<str[b[i].a]<<" "<<str[b[i].b]<<"\n"<<str[b[i].c]<<" "<<str[b[i].d]<<endl;
	return 0;
}

表面上是道紫题 实际上就是紫题

2021/1/22 15:16
加载中...