Pagini recente » Cod sursa (job #1322134) | Cod sursa (job #531546) | Cod sursa (job #1974092) | Cod sursa (job #314737) | Cod sursa (job #1799886)
#include <iostream>
#include <fstream>
void mergeSubarrays(int arr[], int left, int mid, int right){
int i = left, j = mid + 1;
int temp[1000], len = 0;
while(i <= mid && j <= right){
if(arr[i] < arr[j]){
temp[len++] = arr[i++];
}else{
temp[len++] = arr[j++];
}
}
for(; i <= mid; i++){
temp[len++] = arr[i];
}
for(; j <= right; j++){
temp[len++] = arr[j];
}
for(int i = 0; i < len; i++){
arr[left + i] = temp[i];
}
}
void mergeSort(int arr[], int left, int right){
if(left < right){
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
mergeSubarrays(arr, left, mid, right);
}
}
// Cauta binar in intervalul arr[left] ... arr[right] inclusiv primul element care este mai mare decat val si ii returneaza pozitia.
int binarySearch(int arr[], int left, int right, int val){
int mid = (left + right) / 2;
if(left == right){
if(!(arr[left] > val)){
return right + 1;
}else{
return left;
}
}
if(arr[mid] > val){
return binarySearch(arr, left, mid, val);
}else{
return binarySearch(arr, mid + 1, right, val);
}
}
int main(){
std::ifstream fin("nrtri.in");
std::ofstream fout("nrtri.out");
int n, v[1000], k = 0;
fin >> n;
for(int i = 0; i < n; i++){
fin >> v[i];
}
mergeSort(v, 0, n - 1);
//std::cout << binarySearch(v, 0, n - 1, v[5] + v[7]);
for(int i = 0; i < n - 2; i++){
for(int j = i + 1; j < n - 1; j++){
k += binarySearch(v, j + 1, n - 1, v[i] + v[j]) - 1 - j;
//std::cout << k << " ";
}
}
fout << k;
fin.close();
fout.close();
return 0;
}