Pagini recente » Cod sursa (job #2520679) | Cod sursa (job #1239415) | Cod sursa (job #1604153) | Cod sursa (job #3178506) | Cod sursa (job #2622684)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
int n, k;
vector<int> v;
int partition(vector <int>&v, int left, int right)
{
int x = v[right], i = left;
for(int j = left; j < right - 1; j++)
if(v[j] <= x)
{
swap(v[i], v[j]);
i++;
}
swap(v[i], v[right]);
return i;
}
// partition
int kthSmallest(vector<int> &v, int left, int right, int k)
{
if(k > 0 && k <= right - left + 1)
{
int index = partition(v, left, right);
if(index - left == k - 1)
return v[index];
if(index - left > k - 1)
return kthSmallest(v, left, index - 1, k);
return kthSmallest(v, index + 1, right, k - index + left - 1);
}
return 0;
}
int main()
{
fin >> n >> k;
for(int i = 0; i < n; ++i)
{
int x;
fin >> x;
v.push_back(x);
}
fout << kthSmallest(v, 0, n - 1, k);
v.clear();
return 0;
}