Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному

@shatov05 · Регистрация: 09.03.2014

Author24 — интернет-сервис помощи студентам

Задание:

В первой строке входных данных содержатся числа N и K (0NK100001). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2109.

Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

Пример:

Входные данные:
5 4
1 4 5 8 10
5 6 1 9

Выходные данные:
5
5
1
8

http://informatics.mccme.ru/mo... p?id=192#1 - Это задача

C++

#include <iostream>
using namespace std;
const int n = 5 ; //двоичный поиск
int BinarySearch(int a[], int key)
{
    int left = 0, right = n, mid;
    while (left <= right)
    {
        mid = left + (right - left)/2;
        if (key < a[mid]) right = mid-1;
        else if (key > a[mid]) left = mid+1;
        else return mid;
    }
    return -1;
}
//главная функция
void main()
{
    setlocale(LC_ALL,"Rus");
    int i, key, k, n;
    int a[100001], b[100001];
    cin >> n >> k;
    cout<<"Первый массив: ";
    for (i = 0; i < n; i++) //заполнение и вывод массива
    { cin >> a[ i ]; }
    cout<<"Второй массив: ";
    for (int j = 0; j < k; j++){
        cin >> b[ j ];} 
        for ( int j = 0; j < k; j++)   {
            key = b[ j ] ; 
              for ( int i = 0; i < n; i++){ 
    if (BinarySearch(a, key)==-1) cout<<"\nЭлемент не найден";
    else cout<<"\nНомер элемента: "<<BinarySearch(a, key)+1;}}
    system("pause");
}

@DarkerSigner · 17.07.2014, 17:35

Довольно громоздко, но работает

C++

#include <iostream>
using namespace std;
 
int main()
{
    unsigned n=0;
    int k=0;
    cout<<"Enter N and K \n";
    cin>>n>>k;
    int massN[n];
    cout<<"Enter "<<n<<" element massN \n";
    for (int i=0;i!=n;i++)
    cin>>massN[i];
    cout<<"\n";
    int massK[k];
    cout<<"Enter "<<k<<" element massK \n";
    for (int i=0;i!=k;i++)
    cin>>massK[i];
    int temp1=0;
    int temp2=0;
    int massOut[k];
    for (int i=0;i!=k;i++)
        massOut[i]=-1;
    for (int i=0;i!=k;i++)
    {
        for(int j=0;j!=n;j++)
        {
            temp2=0;
            if (massK[i]!=massOut[i])
            if (massK[i]==massN[j])
            {
                massOut[i]=massN[j];
            }
            else
            {
                temp1=massK[i]-massN[j];
                if (temp1<0) temp1*=-1;
                if (massOut[i]!=-1)
                {
                    temp2=massK[i]-massOut[i];
                    if (temp2<0) temp2*=-1;
                    if (temp1<temp2) massOut[i]=massN[j];
                    if (temp1==temp2)
                    {
                        if (massN[j]<massOut[i]) massOut[i]=massN[i];
                    }
                }
                else    massOut[i]=massN[j];
            }
        }
    }
    for (unsigned i=0;i!=k;i++)
        cout<<massOut[i]<<" ";
    return 0;
}

P.S. ввод с клавиатуры, ввод из файла сам сделаешь, там не долго.

@shatov05 · 17.07.2014, 23:23 **[ТС]**

много ошибок...

@Kuzia domovenok · 18.07.2014, 00:07

shatov05, каких конкретно? Ты в ошибках даже не разбираешься, что ли?!!

@DarkerSigner · 18.07.2014, 01:23

shatov05, В чем же ? Я проверил алгоритм по тестовым данным, проходит, вывод верный.

@shatov05 · 18.07.2014, 15:07 **[ТС]**

C++

#include <iostream>
using namespace std;
const int n = 5 ; //двоичный поиск
int BinarySearch(int a[], int key)
{
    int left = 0, right = n, mid;
    while (left <= right)
    {
        mid = left + (right - left)/2;
        if (key < a[ mid ]) right = mid - 1;
        else if (key > a[ mid ]) left = mid + 1;
        else return mid;
    }
    return -1;
}
//главная функция
void main()
{
    setlocale(LC_ALL,"Rus");
    int i, key, k, n;
    int a[100001], b[100001];
    cin >> n >> k;
    cout<<"Первый массив: ";
    for (i = 0; i < n; i++) //заполнение и вывод массива
    { cin >> a[ i ]; }
    cout<<"Второй массив: ";
    for (int j = 0; j < k; j++){
        cin >> b[ j ];} 
        for ( int j = 0; j < k; j++)   {
            key = b[ j ] ; 
    if (BinarySearch(a, key)==-1) cout<<"\nЭлемент не найден"<< endl;
    else cout<<"\nНомер элемента: "<<a [ BinarySearch(a, key) ] << endl;}
    system("pause");
}

выводит ответ : 5 , не найден, 1, не найден..

@SlavaSSU · 18.07.2014, 15:16

я не догоняю, вы сейчас какую задачу решаете? ссылка которую ты дал, там другая задача, там надо для каждого числа найти наиболее близкое к нему, а не сказать, есть оно там или нет.

@DarkerSigner · 18.07.2014, 17:04

shatov05, Ccылку на задачу скидывай правильно. Вот мы тебе и решили ту по которой ссылка, а не ту что хотел.

@shatov05 · 18.07.2014, 22:01 **[ТС]**

Сообщение от DarkerSigner

shatov05, Ccылку на задачу скидывай правильно. Вот мы тебе и решили ту по которой ссылка, а не ту что хотел.

вообще то я правильную ссылку кинул

@SlavaSSU · 18.07.2014, 22:15

shatov05, так проверь.

C++ (Qt)

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> a;
    for(int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
        a.push_back(val);
    }
 
    for(int p = 0; p < m; p++)
    {
        int val;
        scanf("%d", &val);
        int ans1 = 0, ans2 = 0;
        bool ok1 = false, ok2 = false;
        int it = (lower_bound(a.begin(), a.end(), val) - a.begin());
 
        if(it < a.size())
        {
            ans1 = a[it];
            ok1 = true;
        }
 
        if(it > 0)
        {
            it--;
            ans2 = a[it];
            ok2 = true;
        }
 
        if(ok1 && ok2)
        {
            if(abs(ans1 - val) < abs(ans2 - val))
                printf("%d\n", ans1);
            else
                printf("%d\n", ans2);
        }
        else
            if(ok1)
                printf("%d\n", ans1);
            else
                printf("%d\n", ans2);
    }
    return 0;
}

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	18.07.2014, 15:16	26
	я не догоняю, вы сейчас какую задачу решаете? ссылка которую ты дал, там другая задача, там надо для каждого числа найти наиболее близкое к нему, а не сказать, есть оно там или нет. 0

@DarkerSigner 0 / 0 / 0 Регистрация: 17.07.2014 Сообщений: 4
	18.07.2014, 17:04	27
	shatov05, Ccылку на задачу скидывай правильно. Вот мы тебе и решили ту по которой ссылка, а не ту что хотел. 0

@shatov05 0 / 0 / 0 Регистрация: 09.03.2014 Сообщений: 14
	18.07.2014, 22:01 [ТС]	28
	Сообщение от DarkerSigner shatov05, Ccылку на задачу скидывай правильно. Вот мы тебе и решили ту по которой ссылка, а не ту что хотел. вообще то я правильную ссылку кинул 0

@shatov05 0 / 0 / 0 Регистрация: 09.03.2014 Сообщений: 14
	17.07.2014, 23:23 [ТС]	22
	много ошибок... 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	18.07.2014, 00:07	23
	shatov05, каких конкретно? Ты в ошибках даже не разбираешься, что ли?!! 0

@DarkerSigner 0 / 0 / 0 Регистрация: 17.07.2014 Сообщений: 4
	18.07.2014, 01:23	24
	shatov05, В чем же ? Я проверил алгоритм по тестовым данным, проходит, вывод верный. 0

	18.07.2014, 22:15