// #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432 // 我这个是参考的题解的思路(把输入的每个值-k,转化为寻找最长的连续和为0的连续区间,用了前缀和优化)写的,不过我的思路是:记录每个数的第一次和最后一次出现的位置然后相减。题解思路:只记录首次出现时记录位置,然后遍历前缀和数组维护最大值作为答案。 #include <algorithm> #include <array> #include <bitset> #include <cctype> #include <chrono> #include <climits> #include <cmath> //#include <conio.h> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <thread> #include <tuple> #include <unordered_set> #include <vector> //#include <windows.h> using ll = long long int; using namespace std; #define maxn static_cast<int>(1e9 + 10) #define mod static_cast<int>(1e9 + 7) #define mod1 998244353 #define all(_) _.begin(), _.end() #define endl '\n' #define kkk ' ' #define range(var_name, stare, end, step) for (ll var_name = stare; var_name < end; var_name += step) #define pre(var_name, stare, end) for (ll var_name = stare; var_name < end; var_name++) #define erp(var_name, stare, end) for (ll var_name = stare; var_name > end; var_name--) //#define _if(x, pred) |views::filter([&](auto &&x){return pred;}) //#define _map(x, pred) |views::transform([&](auto && x){return pred;}) #define debug(x) cerr << "\nDebuging.." << (#x) << ':' << (x) << endl #define PS putchar(endl),system("pause") #define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define rd read #define pi pair<int, int> #define pll pair<ll, ll> #define pc putchar #define tobe(T, expr) static_cast<T>(expr) //-- #define unde #ifndef unde #define debug(x) void() #define dede #endif #ifdef dede #define strde "\033[47m" << "\033[30m" << "-----------------debug: " << "\033[0m" #endif /*bb_setvalue*/template<typename T>void bb_setvalue(T& bbv_value) { bbv_value = '0'; }template<typename T>void bb_setvalue(std::vector<T>& bbv_vec) { for (auto&& bbv_element : bbv_vec) { bb_setvalue(bbv_element); } } /*bb_make_vector*/template <typename RET> auto bb_make_vector(RET x) { return x; } template <typename T1, typename T2, typename... Args> auto bb_make_vector(T1 m, T2 n, Args... arg) { using InnerType = decltype(bb_make_vector(n, arg...)); return vector<InnerType>(m, bb_make_vector(n, arg...)); } /*read*/template <typename T> inline void read(T& hfv_read_n) { hfv_read_n = 0; T hfv_read_x = 1; char hfv_read_c = getchar(); while (hfv_read_c < '0' || hfv_read_c > '9') { if (hfv_read_c == '-')hfv_read_x = -1; hfv_read_c = getchar(); } while (hfv_read_c >= '0' && hfv_read_c <= '9') { hfv_read_n = (hfv_read_n << 3) + (hfv_read_n << 1) + (hfv_read_c & 15); hfv_read_c = getchar(); } hfv_read_n *= hfv_read_x; } template<typename T1, typename T2, typename ...Args>inline void read(T1& bbv_1, T2& bbv_2, Args&... arg) { read(bbv_1); read(bbv_2, arg...); }template<> inline void read(string& bbv_s) { bbv_s.clear(); char bbv_c = getchar(); while (isspace(bbv_c)) bbv_c = getchar(); while (bbv_c != EOF && !isspace(bbv_c)) { bbv_s.push_back(bbv_c); bbv_c = getchar(); } }template<> inline void read(char& bbv_c) { bbv_c = getchar(); while (isspace(bbv_c)) bbv_c = getchar(); } /*print pr*/template <typename T> inline void print(T hfv_print_n, char hfv_print_c = 0) { if (hfv_print_n < 0) putchar('-'), hfv_print_n = -hfv_print_n; if (hfv_print_n < 10) putchar(hfv_print_n + 48); else print(hfv_print_n / 10), putchar(hfv_print_n % 10 + 48); if (hfv_print_c) putchar(hfv_print_c); } template<typename T> inline void pr(T bbv_value) { print(bbv_value, endl); }template<typename T1, typename T2, typename ...Args> inline void pr(T1 bbv_1, T2 bbv_2, Args... arg) { print(bbv_1, kkk); pr(bbv_2, arg...); } array<int, 8> dirx{ 1,-1,0,0,1,-1,1,-1 }, diry{ 0,0,1,-1,1,1,-1,-1 }; //----------------------------- long long a[static_cast<int>(2e5 + 10)]; void solve() { int n, k; cin >> n >> k; int x; map<long long, int> be, en; be[0] = 0; for (int i = 1; i <= n; i++) { cin >> x; a[i] = x + a[i - 1] - k; if (!be.count(a[i])) be[a[i]] = i; en[a[i]] = i; } vector<pair<long long, int>> hz(en.begin(), en.end()); size_t size = hz.size(); int ans = 0; for (int i = 0; i < size; i++) { ans = max(ans, hz[i].second - be[hz[i].first]); } if (!ans) ans = -1; cout << ans; } /*-----------C-O-D-E----------*/ int main() { #ifdef dede cout << "\033[5m" << "\033[1m" << "DEBUG" << "\033[0m" << endl; #endif // dede int T = 1; //IOS;// cin >> T; //read(T); //---------------- //---------------- #ifdef dede cout << strde << "Enter T: "; cin >> T; #endif // dede while (T--) { #ifdef dede cout << strde << T << endl; #endif solve(); } return 0; } /* ┏┓ ┏┓+ + ┏┛┻━━━┛┻┓ + + ┃ ┃ ┃ ━ ┃ ++ + + + ████━████ ┃+ ┃ ┃ + ┃ ┻ ┃ ┃ ┃ + + ┗━┓ ┏━┛ ┃ ┃ ┃ ┃ + + + + ┃ ┃ Codes are far away from bugs with the animal protecting ┃ ┃ + 神兽保佑,代码大概率无bug(不过神兽偶尔也会休息哦~) ┃ ┃ Blessed by the mythical beast, may bugs stay far away ┃ ┃ + ┃ ┗━━━┓ + + ┃ ┣┓ ┃ ┏┛ ┗┓┓┏━┳┓┏┛ + + + + ┃┫┫ ┃┫┫ ┗┻┛ ┗┻┛+ + +++ */