Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Закрытая тема
Ваша тема закрыта, почему это могло произойти? Возможно,
Нет наработок или кода, если нужно готовое решение - создайте тему в разделе Фриланс и оплатите работу.
Название темы включает слова - "Помогите", "Нужна помощь", "Срочно", "Пожалуйста".
Название темы слишком короткое или не отражает сути вашего вопроса.
Тема исчерпала себя, помните, один вопрос - одна тема
Прочитайте правила и заново правильно создайте тему.
 
Опции темы Поиск в этой теме
Старый 30.03.2018, 11:32   #1
Fanatik
Новичок
Джуниор
 
Регистрация: 30.03.2018
Сообщений: 1
Восклицание Переписать на С++

Есть код Джава, и его необходимо переписать на С++
Код:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Vector;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new FileReader(new File("input.txt")));
        String[] nAuthority = br.readLine().split(" ");
        int n = Integer.parseInt(nAuthority[0]);
        int authority = Integer.parseInt(nAuthority[1]);
        int[] a = new int [n], b = new int [n];
        for (int i = 0; i < n; ++i) {
            String[] ab = br.readLine().split(" ");
            a[i] = Integer.parseInt(ab[0]);
            b[i] = Integer.parseInt(ab[1]);
        }
 
        Friend[] convincesFriends = (new Main(authority, a, b)).convinceMaxFriends();
        BufferedWriter bw = new BufferedWriter(new FileWriter("output.txt"));
        bw.write(convincesFriends.length+"\n");
        for (Friend friend : convincesFriends) {
            bw.write(friend.index+" ");
        }
        bw.flush();
    }
 
    private Friend[] friends;
    private int authority;
    private Main(int authority, int a[], int b[]) {
        this.authority = authority;
        friends = new Friend[a.length];
        for (int i = 0; i < friends.length; ++i) {
            friends[i] = new Friend(a[i], b[i], i+1);
        }
    }
 
    Comparator < Friend > sortCompare = new Comparator<Friend>() {
        @Override
        public int compare(Friend o1, Friend o2) {
            return o2.a+o2.b-o1.a-o1.b;
        }
    };
 
    private Friend[] solveNegativeDp(Friend[] negative) {
        Arrays.sort(negative, sortCompare);
 
        Integer[][] maxBSum = new Integer[negative.length+1][negative.length+1];
        maxBSum[0][0] = 0;
        for (int i = 1; i <= negative.length; ++i) {
            maxBSum[i][0] = 0;
            for (int j = 1; j <= negative.length; ++j) {
                if (maxBSum[i-1][j-1] != null && authority + maxBSum[i-1][j-1] >= negative[i-1].a) {
                    maxBSum[i][j] = maxBSum[i-1][j-1] + negative[i-1].b;
                }
                if (maxBSum[i][j] == null || maxBSum[i-1][j] != null && maxBSum[i-1][j] >= maxBSum[i][j]) {
                    maxBSum[i][j] = maxBSum[i-1][j];
                }
            }
        }
 
        int j, i = negative.length;
        for (j = negative.length; maxBSum[i][j] == null; --j);
 
        Friend[] negativeAdded = new Friend[j];
        for (; i >= 0 && j > 0; --i) {
            if (maxBSum[i][j] != maxBSum[i-1][j]) {
                negativeAdded[--j] = negative[i-1];
            }
        }
 
        return negativeAdded;
    }
 
    private Friend[] solveNegativeGreedy(Friend[] negative) {
        Arrays.sort(negative, sortCompare);     
 
        PriorityQueue<Friend> negativeAdded = new PriorityQueue<>(1, new Comparator<Friend>() {
            @Override
            public int compare(Friend o1, Friend o2) {
                return o1.b - o2.b;
            }
        });     
        for (Friend friend : negative) {
            if (authority >= friend.a) {
                authority += friend.b;
                negativeAdded.add(friend);
            } else if (!negativeAdded.isEmpty() && authority - negativeAdded.peek().b >= friend.a && negativeAdded.peek().b < friend.b) {
                authority = authority - negativeAdded.poll().b + friend.b;
                negativeAdded.add(friend);
            }
        }
 
        Friend[] answer = negativeAdded.toArray(new Friend[negativeAdded.size()]);
        Arrays.sort(answer, sortCompare);
        return answer;
    }
 
    private Friend[] convinceMaxFriends(){
        Vector < Friend > convinced = new Vector<>();
        Vector < Friend > positive = new Vector<>();
        for (int i = 0; i < friends.length; ++i) {
            if (friends[i].b >= 0) {
                positive.add(friends[i]);
            }
        }
 
        positive.sort(new Comparator<Friend>() {
            @Override
            public int compare(Friend o1, Friend o2) {
                return o1.a - o2.a;
            }
        });
 
        for (Friend friend : positive) {
            if (authority >= friend.a) {
                authority += friend.b;
                convinced.add(friend);
            }
        }
 
        Friend[] negative = new Friend[friends.length - positive.size()];
        for (int i = 0, j = 0; i < friends.length; ++i) {
            if (friends[i].b < 0) {
                negative[j++] = friends[i];
            }
        }
 
 
        convinced.addAll(Arrays.asList(solveNegativeGreedy(negative)));
 
        return convinced.toArray(new Friend[convinced.size()]);
    }
 
    private class Friend {
        private int a, b, index;
        private Friend(int a, int b, int index) {
            this.a = a;
            this.b = b;
            this.index = index;
        }
    }
 
}
Fanatik вне форума
Старый 30.03.2018, 11:34   #2
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Тут не решатель задач.

Назовите нормально тему, покажите свои наработки, конкретные вопросы и т.п.
http://www.programmersforum.ru/announcement.php?f=31

Или в раздел Фриланс если вы не хотите ничего делать, а ищете кого-то, кто выполнит ваши задачи за вознаграждение.
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.
Alex11223 вне форума
Закрытая тема


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Переписать с c++ на c# 5ss Помощь студентам 0 09.04.2016 00:28
Переписать из c++ в c Pushok! Помощь студентам 4 08.10.2015 21:25
не могу переписать на с++ Хорёк C++ Builder 0 12.06.2012 20:30
переписать программу геннадий522 Visual C++ 2 18.12.2011 14:46
Переписать insolent Общие вопросы C/C++ 6 24.08.2010 14:32