Unsorted Ideas::
This is a paging/caching type problem.
Normally we see the online version of this problem, suppose while caching we have a maximum limit of web pages our cache can contain.
When a user submits query for a webpage, server first takes a look at the cache memory. if its there , server crawls the page from the cache. Hence, we dont need to undergo the cost of bringing the page from the server which is 1 chf according to the problem. :v
সেইমভাবে, আমাদের একটা লাইব্রেরি আছে, আরেকটা বুক স্টোর আছে । লাইব্রেরির নির্দিষ্ট ক্যাপাসিটি আছে। এর বেশি নিতে পারে না বই লাইব্রেরী ।
প্রতিদিন বিভিন্ন ইউজার আসবে এবং বিভিন্ন নাম্বার বইটা পড়তে চাইবে। ওই যে একটু আগের ওয়েব পেজ কোয়েরির মত, বই কোয়েরি করবে।
যদি লাইব্রেরি থাকে তাহলে লাইব্রেরিয়ান তোমাকে বইটা দিবে। এতে লাইব্রেরিয়ানের কোন খরচ পড়বে না।
আর যদি আগে থেকে লাইব্রেরি তে না থাকে বইটি, তবে পার্শ্ববর্তী দোকান থেকে বইটি কিনে আনতে হবে। এতে এক ডলার করে খরচ পড়বে।
ইনিশায়ালি লাইব্রেরি খালি থাকবে, কোন বই থাকবে। স্বাভাবিক, ইনিশিয়ালি ক্যাশ এ কোন ওয়েব পেজ ফেচ করে আনা থাকে না।
অরিজিনাল ওয়েব পেজ ক্যাশিং সিস্টেম এ, কোয়েরি থাকে অনলাইন। মানে কেউ জানে না ইউজার তারপর কি কোয়েরি করবে।
বাট নাও, লেট আস সি দ্য, অফলাইন ভারশান অফ দ্য প্রব্লবেম । মানে আমাদের একটা সিকুয়েন্স অফ নাম্বারস i.e. সিকুয়েন্স অফ কোয়েরিস অফলাইন, মানে মানে আগে থেকে দেয়া থাকবে।
তার সাথে ক্যাশের ম্যাক্স সাইজ মানে লাইব্রেরীর ম্যাক্স ধারণ ক্ষমতা দিয়ে দিবে।
আমাদের বলতে হবে, সবচেয়ে ইফশিয়েন্ট ওয়েতে কিভাবে ক্যাশিং করলে আ
মরা সবচেয়ে কম কস্টে সার্ভিস দিতে পারব।
Code ::
// aarifshuvo ``CSEJU
#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
using namespace std;
#define inf 123456789
#define sz 400007
ll ar[sz], nx[sz];
map<ll,ll> mp;
int main()
{
ll n,k;
scll(n,k);
REP(i,n)
{
scl(ar[i]);
mp[ ar[i] ] = INT_MAX;
//ধরে নিচ্ছি সবগুলা নাম্বারের কোন রিপিটিশান হয় নি , সব INT_MAX দিয়ে আপডেট করছি ।
}
REV(i,n) //উলটা দিক থেকে আসছি
{
nx[i] = mp[ ar[i] ];
//শেষ থেকে শুরুতে যাচ্ছি যেহেতু, প্রথম এপিয়ারেন্স এ তাই এর নেক্সটে আর রিপিট
// হবার কোন পসিবিলিটি নাই , তাই ইনফিনিটি দিয়ে দিচ্ছি। মানে রিপিট নাই পরে আর।
mp[ ar[i] ] = i;
//mp[ar[i]] কে লেটেস্ট এপিয়ারেন্স এর পজিশান অ্যাাসাইন করে দিচ্ছি ,
// যাতে অ্যাারের আগের দিকে কোথাও এই নাম্বার আবার আসলে এইটা ইউজ করতে পারি।
}
//প্রথমে nx[] নামে একটা অ্যাারে বানাতে হবে, ক্যাশ থেকে আমরা যখন জিনিসপত্র ডিলিট করে দিব,
// তখন জানা দরকার , ওই ইন্ডেক্সের রিকোয়েস্টড নাম্বারটি নেক্সট কখন রিপিট করছে
// সেই অনুযায়ী, আমরা নেক্সট রিপিটিং টাইম অনুযায়ী , প্রত্যেক ইন্ডেক্সের জন্য
// নেক্সট রিপিটিং টাইমটা যদি সেট এ রেখে দিই, তাহলে আমরা যখনি ক্যাশ/সেট টা ফিল হয়ে যাবে
// তখন সবচেয়ে বেশি দূরবর্তী রিপিটিং টাইম ওয়ালা রিকুয়েস্ট টি যেটা সেটের শেষে থাকবে স্বভাবতই,
// আপাতত সেটি ডিলিট করে দিয়ে, কারেন্ট বই এর জন্য জায়গা করে দিতে পারি লাইব্রেরিতে :p
set<ll> st; //ইনিশিয়ালিজিং দা ক্যাশ, ক্যাশেও কোন রিপিট থাকবে না, সেট ও থাকবে না তাই :V
ll cnt = 0;
REP(i,n)
{
//৫ ৩
// ১ ২ ১০ ২ ১০
// প্রথম ১০ দ্বিতীয় ১০ , দ্বিতীয় ১০ এ যখন যাব দেখবে যে এটি আগে থেকেই আছে।
//তো আমাদের এইটা আর আগেরটা নেক্সট টাইম এইটা আর দরকার নাই। আমাদের দরকার , দ্বিতীয় দশ এর
//নেক্সট পজিশান , তাই আগের দশের নেক্সট পজিশান মানে বর্তমান ১০ এর ইন্ডেক্স i কে রিমুভ করছি
// আমরা ক্যাশ থেকে। পরে আবার নিচে nx[i] ইনসারট করছি কিন্তু ।
if(st.count( i ))
{
st.erase( i );
//রিমুভিং দ্য কারেন্ট পজিশান
}
else
{
cnt ++ ;
//এডিং কস্ট ফর বায়িং দ্য বুক ইচ টাইম, ফ্রম বুক স্টোর টু লাইব্রেরি
}
if(SZ(st) == k) //লাইব্রেরি ফুল হয়ে গ্যাছে , তাই
{
st.erase( --st.end() );
//ডিলিটিং দ্য লেট(দেরী) মোস্ট ওয়ান , রিকুয়েস্ট
}
st.insert( nx[i] );
// ইনসারটিং দ্য নেক্সট রিপিটিং টাইম অফ দ্য কারেন্ট রিকুয়েস্ট
}
printf("%lld\n", cnt);
return 0;
}
Clean Code :
// aarifshuvo ``CSEJU
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;
#define inf 12345678912
#define sz 400007
ll ar[sz], nx[sz];
map<ll,ll> mp;
int main()
{
ll n,k;
scll(n,k);
REP(i,n)
{
scl(ar[i]);
mp[ ar[i] ] = INT_MAX;
}
REV(i,n)
{
nx[i] = mp[ ar[i] ];
mp[ ar[i] ] = i;
}
set<ll> st;
ll cnt = 0;
REP(i,n)
{
if(st.count( i ))
{
st.erase( i );
}
else
{
cnt ++ ;
}
if(SZ(st) == k)
{
st.erase( --st.end() );
}
st.insert( nx[i] );
}
printf("%lld\n", cnt);
return 0;
}
