المقطع المميز
الزمن المحدد: 1 ثانية الذاكرة المحددة: 256 ميجابايت
أُعطيت مصفوفة تحتوي على \(n\) عددًا صحيحًا.
يُسمى مقطع من المصفوفة مميزًا إذا كانت جميع العناصر داخله مختلفة زوجيًا.
مهمتك هي إيجاد أكبر طول ممكن لمقطع متصل ومميز.
بعبارة أخرى، أوجد أكبر قيمة لـ \(r-l+1\) بحيث تكون جميع الأعداد \(a_l,\ a_{l+1},\ \ldots,\ a_r\) مختلفة.
المدخلات
يحتوي السطر الأول على عددين صحيحين \(n\) و\(s\)، حيث \(1 \le n \le 2 \cdot 10^5\).
حيث:
- \(n\) هو عدد عناصر المصفوفة.
- \(s\) هو رقم المهمة الجزئية.
يحتوي السطر الثاني على \(n\) عددًا صحيحًا \(a_1,\ a_2,\ \ldots,\ a_n\)، حيث \(1 \le a_i \le 10^9\).
المخرجات
اطبع عددًا صحيحًا واحدًا: أكبر طول لمقطع متصل تكون جميع عناصره مختلفة.
التقييم
تتكون المسألة من عدة مهام جزئية. لكل مهمة جزئية قيود إضافية وعدد محدد من النقاط.
| المهمة الفرعية | قيود إضافية | النقاط |
|---|---|---|
| \(1\) | جميع القيم مختلفة | \(3\) |
| \(2\) | \(n \le 200\) | \(7\) |
| \(3\) | \(n \le 2000\) | \(8\) |
| \(4\) | \(1 \le a_i \le 100\) | \(7\) |
| \(5\) | \(1 \le a_i \le 1000000\) | \(11\) |
| \(6\) | الإجابة لا تقل عن \(n-1\) | \(8\) |
| \(7\) | المصفوفة غير متناقصة | \(13\) |
| \(8\) | توجد قيمة واحدة على الأكثر تظهر أكثر من مرة | \(18\) |
| \(9\) | لا توجد قيود إضافية | \(25\) |
المجموع الكلي للنقاط هو \(100\) نقطة.
أمثلة
المدخلات
8 9
1 2 1 3 4 2 3 5المخرجات
4الملاحظات
في المثال، أحد المقاطع المميزة الصالحة هو من الموضع \(3\) إلى الموضع \(6\): \(1,\ 3,\ 4,\ 2\).
جميع العناصر في هذا المقطع مختلفة، وطوله هو \(4\).
ويمكن إثبات أنه لا يوجد مقطع متصل ومميز طوله \(5\) أو أكثر.
لذلك، فإن الإجابة هي \(4\).
الحل
حافظ على نافذة منزلقة ذات قيم مختلفة. عند كل طرف أيمن، تذكر آخر موضع ظهرت فيه قيمته. إذا كان داخل النافذة الحالية فحرّك الطرف الأيسر إلى ما بعده. يدخل كل موضع النافذة ويخرج منها مرة واحدة. التعقيد المتوقع \(O(N)\) باستخدام جدول تجزئة، والذاكرة \(O(N)\). رقم المهمة الفرعية \(s\) لا يغير الخوارزمية.
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, subtask;
cin >> n >> subtask;
unordered_map<long long, int> lastPosition;
int left = 0;
int answer = 0;
for (int right = 0; right < n; right++) {
long long value;
cin >> value;
auto it = lastPosition.find(value);
if (it != lastPosition.end()) {
left = max(left, it->second + 1);
}
lastPosition[value] = right;
answer = max(answer, right - left + 1);
}
cout << answer << '\n';
}