题目描述

F4拉力赛在一个环形公路上举行，主办方为了拉来更多赞助，在环形公路每间隔一米就设立一块广告牌。

假设赛车的速度为 x 米/秒，请问赛车在一秒内经过最多数量的广告牌编号是什么？

输入描述

第一行输入一个数组，数组元素是环形公路上的广告牌编号，数组头尾元素可以认为相邻。输入格式见用例。数组长度最大 1000000。数组元素是正整数不大于100。

第二行输入赛车速度 x 米/秒。用例保证 x 不大于数组长度。

输出描述

请输出赛车一秒内经过最多数量的广告牌编号。

若有多个最多数量的广告牌编号，则输出最小的。

用例

输入

[3,1,2,3]
2

Copy

输出

3

 

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e6 + 10;void solve() {//处理字符串string str;getline(cin, str);str = str.substr(1, str.size() - 2); vector<int> v;size_t pos = 0;while ((pos = str.find(',')) != string::npos) {v.push_back(stoi(str.substr(0, pos)));str.erase(0, pos + 1);}v.push_back(stoi(str)); int x;cin >> x;map<int, int> mp;v.insert(v.end(), v.begin(), v.end()); //处理回环问题int res = 0, maxx = -1;//滑动寻找答案for (int l = 0, r = 0; r < v.size(); r++) {if (r - l >= x) {mp[v[l]]--;if (mp[v[l]] == 0) {mp.erase(v[l]); }l++;}mp[v[r]]++;if (mp[v[r]] > maxx) {maxx = mp[v[r]];res = v[r];} else if (mp[v[r]] == maxx) {res = min(res, v[r]);}// cout<<mp[v[r]]<<endl;}cout << res << endl;
}signed main() {solve();return 0;
}