ধরা যাক, কোন স্কুলের রেজাল্ট করা হবে। একটি খাতায় ছক করা হল। এক পাশে ছাত্র ছাত্রীদের নাম
আর এক পাশে থাকবে তাদের নম্বর । এখন যারা বেশি নম্বর পাবে তারাই ক্রমিক নম্বরে এগিয়ে থাকবে। এই ভাবে বেশি নম্বর অনুযায়ী নামগুলো সর্ট হয়ে রেজাল্ট তৈরী হবে।
এখানে কিন্তু নম্বর এর উপর নির্ভর করে নামগুলো সর্ট হচ্ছে। তাই এখানে ভেক্টর এ থাকছে নাম ও নম্বর এর জোড় (পেয়ার) ।
আর একটি বিষয় হল, যদি একই নম্বর অনেক জন পায় তাহলে পুর্বে তাদের রোল যত ছিল সর্ট করার পর ও তাই থাকবে। এক্ষেত্রে স্ট্যাবল সর্ট ব্যবহার করতে হবে।
সি প্লাস প্লাস এর বিল্ট ইন stable_sort ব্যবহার করে এই সর্ট করা যাবে। যেহেতু পেয়ার এর দ্বিতীয় উপাদান অনু্যায়ী সর্ট করব তাই ভেক্টর এ পেয়ার নিয়ে নিব । এর পর স্ট্যাবল সর্ট এর মধ্যে ভেক্টর টিকে নিয়ে নিব। এখানে compare ফাংশন ব্যবহার করতে হবে কারন সটিং Ascending না Descending হবে তা বুঝিয়ে দেয়ার জন্য। যেহেতু বেশি নম্বর অনূযায়ী সর্ট করব তাই এখানে Descending compare ফাংশন ব্যবহার করব।
আর একটি গুরুত্ত্বপূর্ন বিষয় হল Single Sorting এর সময় আমরা শুধু sort ব্যবহার করি। এই sort function হল কুইক সর্ট । আর stable_sort function টি হল মার্জ সর্ট ।
Code :
#include <bits/stdc++.h>
using namespace std;
bool compare( const pair<string,long long int>& x, const pair<string, long long int>& y )
{
return (x.second>y.second); //descending
}
int main()
{
vector<pair<string,long long int> >a;
long long int n,i,j,b,c;
string s;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>s>>c;
a.push_back(make_pair(s,c));
}
stable_sort(a.begin(),a.end(),compare);
vector<pair<string,long long int> >::iterator p;
cout<<endl;
for(p=a.begin();p!=a.end();p++)
{
cout<<p->first<<" "<<p->second<<endl;
}
return 0;
}
Related Online Judge Problems :
ACM Timus 1100. Final Standings
Solution :
#include <bits/stdc++.h>
using namespace std;
bool compare( const pair<long long int,long long int>& x, const pair<long long int, long long int>& y )
{
return (x.second>y.second); //descending
}
int main()
{
vector<pair<long long int,long long int> >a;
long long int n,i,j,b,c;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>b>>c;
a.push_back(pair<long long int,long long int>(b,c));
}
stable_sort(a.begin(),a.end(),compare);
vector<pair<long long int,long long int> >::iterator p;
for(p=a.begin();p!=a.end();p++)
{
cout<<p->first<<" "<<p->second<<endl;
}
return 0;
}
Codeforces Beta Round #59 (Div. 2) A. Sinking Ship
Solution:
#include <bits/stdc++.h>
using namespace std;
bool compare( const pair<string,string>& x, const pair<string, string>& y )
{
return (x.second<y.second); //ascending
}
int main()
{
vector<pair<string,string> >s;
int n,i,j;
string a,b,c;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a>>b;
if(b=="rat")
{
c="1";
}
else if(b=="woman")
{
c="2";
}
else if(b=="child")
{
c="2";
}
else if(b=="man")
{
c="3";
}
else if(b=="captain")
{
c="4";
}
s.push_back(make_pair(a,c));
}
stable_sort(s.begin(),s.end(),compare);
vector<pair<string,string> >::iterator p;
for(p=s.begin();p!=s.end();p++)
{
cout<<p->first<<endl;
}
return 0;
}
ACM EPOKA Mr Li Criteria Solution
Sorting Columns array based on several conditions
#include <bits/stdc++.h>
using namespace std;
bool comparename( const pair<string,long long int>& x, const pair<string, long long int>& y )
{
if(x.first.size()==y.first.size())
{
if(x.second==y.second)
{
return x.first<y.first;
}
return x.second<y.second;
}
return x.first.size()<y.first.size();
}
int main()
{
vector<pair<string,long long int> >a;
set<pair<string,long long int> >myset;
vector<string>ss;
vector<long long int>gd;
long long int n,i,j,b,c,cnt=0,l,sh;
string s;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
cin>>n>>sh;
for(i=1;i<=n;i++)
{
cin>>s>>c;
a.push_back(make_pair(s,c));
}
sort(a.begin(),a.end(),comparename);
vector<pair<string,long long int> >::iterator p;
for(p=a.begin();p!=a.end();p++)
{
if(cnt==sh)
{
break;
}
cout<<p->first<<" "<<p->second<<endl;
cnt++;
}
return 0;
}
0 comments:
Post a Comment