输入
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; }
