题目:狐进行了一次黑客马拉松大赛,全公司一共分为了N个组,每组一个房间排成一排开始比赛,比赛结束后没有公布成绩,但是每个组能够看到自己相邻的两个组里比自己成绩低的组的成绩,比赛结束之后要发奖金,以1w为单位,每个组都至少会发1w的奖金,另外,如果一个组发现自己的奖金没有高于比自己成绩低的组发的奖金,就会不满意,作为比赛的组织方,根据成绩计算出至少需要发多少奖金才能让所有的组满意。
输入描述:
每组数据先输入N,然后N行输入N个正整数,每个数表示每个组的比赛成绩。
输出描述:
输出至少需要多少w的奖金
输入例子:
10
20
32
12
32
45
11
21
31
41
33
输出例子:
20
解答:
牛客网真是神奇……
愣是说我没有输出……
我建立了一个二维的vector,分别放分数和对应的奖金,大家初始都是1
然后检查每一个组,
如果比自己分数低,并且奖金大于等于自己,则比对方的奖金多1
如果两边都是同样的情况,则比奖金高的一方加一
说实话的确不是最快的算法,但是是最好想的
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 using namespace std; 5 6 int main() { 7 int n, sum = 0; 8 bool flag = 1; 9 vector<vector<int>> v; 10 vector<int> v2(2,0); 11 cin >> n; 12 v.push_back(v2); 13 v2[1] = 1; 14 for (size_t i = 0; i < n; i++) 15 { 16 cin >> v2[0]; 17 v.push_back(v2); 18 } 19 v2[0] = 0; 20 v2[1] = 0; 21 v.push_back(v2); 22 while (flag) 23 { 24 flag = 0; 25 for (size_t i = 1; i < n + 1; i++) 26 { 27 if (v[i][0] > v[i - 1][0]&& v[i][1] <= v[i - 1][1]) { 28 flag = 1; 29 if (v[i][0] > v[i + 1][0]) 30 { 31 v[i][1] = v[(v[i - 1][1] > v[i + 1][1] ? (i - 1) : (i + 1))][1] + 1; 32 } 33 else 34 { 35 v[i][1] = v[i - 1][1] + 1; 36 } 37 } 38 else 39 { 40 if (v[i][0] > v[i + 1][0] && v[i][1] <= v[i + 1][1]) { 41 flag = 1; 42 v[i][1] = v[i + 1][1] + 1; 43 } 44 } 45 } 46 } 47 48 /* 49 for (size_t i = 0; i < n; i++) 50 { 51 cout << v[i][1] << " "; 52 } 53 cout << endl; 54 */ 55 for (size_t i = 1; i < n + 1; i++) 56 { 57 //cout << v[i][0] << " "; 58 sum += v[i][1]; 59 } 60 cout << sum; 61 62 }