题目描述
输入
3
4 2 3 1 10 5 9 7
输出
1
思路1:模拟+构建哈夫曼树, 当只剩下两个节点时,就是一个是冠军一个是亚军.
参考代码
#include<bits/stdc++.h>
#include<queue>
using namespace std;
typedef struct {
int score;
int loc;
}Node;
queue<Node> Q;
int n;
Node w1, w2;
int main() {
cin >> n;
int w = 1 << n;
//cout<<w;
for (int i = 0; i < w; i++) {
Node node;
cin >> node.score;
node.loc = i + 1;
Q.push(node);
}
while (Q.size() != 2) {
w1 = Q.front();
Q.pop();
w2 = Q.front();
Q.pop();
w1.score > w2.score ? Q.push(w1) : Q.push(w2);
//cout<<"----------------"<<endl;
}
w1 = Q.front();
Q.pop();
w2 = Q.front();
Q.pop();
if (w1.score > w2.score) {
cout << w2.loc << endl;
}
else {
cout << w1.loc << endl;
}
return 0;
}
思路2:可以把串分成前后两部分,前半部分的最高分和后半部分的最高分进行比较,胜利的便为冠军,失败的为亚军.
参考代码
#include<bits/stdc++.h>
using namespace std;
typedef struct {
int score;
int loc;//位置
} Node;
bool cmp(Node x,Node y) {
return x.score<y.score;
}
Node arr[(1<<7)+10];
int n,num;
int main() {
cin>>n;
num = 1<<n;
for(int i = 1; i <= num; i++) {
cin>>arr[i].score;
arr[i].loc = i;
}
sort(arr+1,arr+num/2+1,cmp);//arr,arr+n 0 4
sort(arr+num/2+1,arr+num+1,cmp);//arr 0 arr+1:1 arr+num/2
if(arr[num/2].score > arr[num].score) {
cout<<arr[num].loc<<endl;
} else {
cout<<arr[num/2].loc<<endl;
}
return 0;
}