浙江理工大学校赛 C 仓鼠的约会大作战（模拟）
4388: 仓鼠的约会大作战
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 457 Solved: 63
Description
仓鼠有n个二次元老婆，第 i 个老婆的美丽度为 xi .
现在仓鼠打算让她们打一架，决出心中的 No.1和No.2, 规则如下：
每一轮从左到右处于奇数位的先和各自右边的打一架，然后从左到右处于偶数位的再和各自右边的打一架。
打一架的规则为：
美丽度高的获胜，获胜方美丽度立即加1，失败方美丽度立即减1，如果打架双方美丽度一样，就同时淘汰，不参加下一次的“打一架”。
每次打一架结束后，如果当前人数小于等于2个人，仓鼠就会立刻停止这个比试。
每一轮结束后，美丽度最低的老婆会被淘汰，如果有多个老婆美丽度并列最低，则除去编号最小的那个，之后如果当前人数小于等于2个人，仓鼠就会立刻停止这个比试。
请问最后剩下的两名老婆是谁？请从小至大的输出她们的编号，中间用一个空格隔开。如果最后不能剩下两名，请输出“impossible”。
Input
第一行有一个整数T，代表接下来会有T组数据。
对于每组数据，第一行有一个整数n。
对于每组数据，第二行有n个整数a1,a2…an，第i个数代表第i个老婆的美丽度。
Output
对于每组数据输出一行，按从小到大的顺序输出两个整数编号，代表最后剩下的那两个老婆的编号。两个整数间有一个空格隔开，如果最后不能剩下两名，请输出“impossible”。
Sample Input
Sample Output
HINT
T <= 50
n <= 1000
ai <= 1e9
样例解释：
第一 组数据：（i，j）表示aj = i；
第一轮第一次打架，1号和2号同归于尽，4号赢了3号
结束时 （1,3）（4,4）（3,5）
第一轮第二次打架结束时 （1,3）（5,4）（2,5）
第一轮结束时3号被淘汰
所有最后答案时4，5；
第二组数据：
第一轮第一次打架结束时 （5,1）（2,2）（4,3）（7,4）
第一轮第二次打架结束时 （5,1）（1,2）（5,3）（7,4）
第一轮结束时 （5,1）（5,3）（7,4）
第二轮第一次打架结束时 （7,4）
没什么技巧，就是根据题目的意思模拟就好了，第一次一直让cnt++
虽然Ac了但是发现内存占用的有点大，并且vector必须开到3000。
然后做了一点优化，其实用过的清空后可以再用，滚动起来就好了。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define LL long long
using namespace std;
#define N 1005
#define debug cout<<"debug***********"<<endl;
struct node
{
int k,p;
};
vector<node>V[10];
int cnt=0;
int work(int n)
{
for(int i=0;i+1<n;i+=2)
{
if(V[cnt][i].k<V[cnt][i+1].k)
{
V[cnt][i].k--;
V[cnt][i+1].k++;
V[cnt+1].push_back(V[cnt][i]);
V[cnt+1].push_back(V[cnt][i+1]);
}
else if(V[cnt][i].k>V[cnt][i+1].k)
{
V[cnt][i].k++;
V[cnt][i+1].k--;
V[cnt+1].push_back(V[cnt][i]);
V[cnt+1].push_back(V[cnt][i+1]);
}
}
if(n&1==1)
{
V[cnt+1].push_back(V[cnt][n-1]);
}
cnt++;
if(V[cnt].size()<=2)return V[cnt].size();
n=V[cnt].size();
V[cnt+1].push_back(V[cnt][0]);
for(int i=1;i+1<n;i+=2)
{
if(V[cnt][i].k<V[cnt][i+1].k)
{
V[cnt][i].k--;
V[cnt][i+1].k++;
V[cnt+1].push_back(V[cnt][i]);
V[cnt+1].push_back(V[cnt][i+1]);
}
else if(V[cnt][i].k>V[cnt][i+1].k)
{
V[cnt][i].k++;
V[cnt][i+1].k--;
V[cnt+1].push_back(V[cnt][i]);
V[cnt+1].push_back(V[cnt][i+1]);
}
}
if(n%2==0)
{
V[cnt+1].push_back(V[cnt][n-1]);
}
V[cnt].clear();
cnt++;
if(V[cnt].size()<=2)return V[cnt].size();
int l=V[cnt].size();
int m=0x3f3f3f3f,pos=0;
for(int i=0;i<l;i++)
{
if(V[cnt][i].k<m)
{
m=V[cnt][i].k;
pos=i;
}
}
for(int i=0;i<cnt;i++)
{
V[i].clear();
}
for(int i=0;i<l;i++)
{
if(i==pos)continue;
V[0].push_back(V[cnt][i]);
}
V[cnt].clear();
cnt=0;
return V[0].size();
}
int judge(int k)
{
if(k>2)return 1;
else return 0;
}
void init( )
{
for(int i=0;i<10;i++)
{
V[i].clear();
}
cnt=0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
init();
int n;
cin>>n;
node tem;
for(int i=1;i<=n;i++)
{
cin>>tem.k;
tem.p=i;
V[cnt].push_back(tem);
}
int m = n;
while(1)
{
if(m<=2)break;
m=work(m);
}
if(m==2)
{
cout<<V[cnt][0].p<<" "<<V[cnt][1].p<<endl;
}
else cout<<"impossible"<<endl;
}
}
相关知识
猫咪模拟大作战安装下载
猫咪模拟大作战中文版游戏APP下载
仓鼠大作战单机游戏下载
模拟人生3宠物 狗怎么学会寻找收藏品、帮助约会、打猎
仓鼠迷宫大作战常见问题
手工｜模拟养仓鼠 沉浸式模拟养宠物 自制纸宠物
球球大作战仓鼠宝宝限定套装礼盒 仓鼠宝宝皮肤
模拟养宠物的游戏合集
拍摄大作战
石家庄理工职业学院—现代职业教育践行者
网址: 浙江理工大学校赛 C 仓鼠的约会大作战（模拟） https://m.mcbbbk.com/newsview707288.html
| 上一篇: 仓鼠竞赛安卓版下载安装 |
下一篇: 广元宠物猫品种价钱 |
