Форум программистов, компьютерный форум CyberForum.ru

Как работает эта программа? - C++

Восстановить пароль Регистрация
 
Levk
0 / 0 / 0
Регистрация: 22.02.2012
Сообщений: 4
22.02.2012, 09:10     Как работает эта программа? #1
Помогите пожалуйста построчно/блочно определить, что делается в программе. Заранее благодарю!

Задача
На стороне оператора установлен SMS шлюз, который по некоторому протоколу принимает сообщения и передаёт их конечным абонентам. У шлюза есть память, которая может хранить не более M сообщений.
Шлюз работает циклично, каждый цикл состоит из следующих шагов:
1) Шлюз принимает заявки на отправку сообщений от всех провайде-ров. Каждая заявка содержит количество сообщений для отправки и стои-мость одного сообщения. Все сообщения в одной заявке имеют одинаковую стоимость.
2) Шлюз анализирует заявки и сохраненные в памяти сообщения, после чего запрашивает у провайдеров не более M сообщений для последующей отправки.
3) Все запрошенные сообщения сохраняются в память, при необходимости затирая старые.
4) Шлюз отправляет не более N сообщений из своей памяти, все от-правленные сообщения удаляются из памяти.
5) Если в памяти остались сообщения, то цена каждого сообщения уменьшается на 1 копейку, если цена становится нулевой сообщение удаля-етсяиз памяти. После чего шлюз переходит к следующему циклу.
Определить, сколько сообщений будет доставлено, сколько будет потеряно и сколько денег будет заработано, если известно, что на начало работы сообщений в памятине было, и шлюз работал по оптимальномуалгоритму позволяющему заработать как можно больше денег.

Входные данные

Первая строка входа содержит количество тестов. Первая строка каждого теста содержит три числа K, N, M. K – количество циклов работы шлюза (1<=K<=100). N – максимальное количество сообщений, которое может отправить шлюз за один цикл (1<=N<=1000000). M – количество сообщений, сохраняемое в памяти шлюза (1<=M<=1000000). Далее следует K строк с описанием заявок принятых в каждом цикле работы шлюза. В начале каждой строкизадается число P - количество заявок, полученных в данном цикле, далее следует Pпар чисел, описывающих параметры заявки:n– количество сообщений и c- стоимость одного сообщения в копейках (0<P<=100, 0<n<=1000, 0<c<=1000). Работа шлюза заканчивается после Kцикла, оставшиеся в памяти сообщения считаются потерянными.

Выходные данные

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

Пример входных данных Пример выходных данных
1 75 150 325
2 100 50
1 200 3
1 25 7

Решение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <algorithm>
using namespace std;
 
struct package
{
    package()
    {}
    package(int c, int m): count(c), money(m)
    {}
    int count, money;
 
};
 
bool cmp (package &f, package &s)
{
    return f.money >s.money;
}
 
typedef vector<package>::iterator pi;
 
int main()
{
    freopen("gateway.in", "r", stdin);
    freopen("gateway.out", "w", stdout);
 
    vector<package> pack, next;
    pack.reserve(100*100);
    next.reserve(100*100);
 
    int testn;
    cin >> testn;
    for(int test = 0; test < testn; test++)
    {
        long long send = 0, lost = 0, money = 0;
        int k, n, m;
        cin >> k >> n >> m;
 
        assert(1<=k && k<=100);
        assert(1<=n && n<=1000000);
        assert(1<=m && m<=1000000);
 
        for(int iter=0; iter<k; iter++)
        {
            int p;
            cin >> p;
            assert(1<=p && p<=100);
            for(int i=0; i<p; i++)
            {
                package cur;
                cin >> cur.count >> cur.money;
 
                assert(1<=cur.count && cur.count<=1000);
                assert(1<=cur.money && cur.money<=1000);
                next.push_back(cur);                
            }
 
            sort(next.begin(), next.end(), cmp);
            
            int mem = 0;
            pi pos = next.begin();
            while(mem < m && pos!=next.end())
            {
                int add = min(m-mem, pos->count);
                mem+=add;
                package cur(add, pos->money);
                pack.push_back(cur);
                pos->count -= add;      
                pos++;
            }
 
            for(pi i = next.begin(); i!= next.end(); i++)
            {
                lost += i->count;
            }
 
            int s = 0;
            pos = pack.begin();
            while(s < n && pos != pack.end())
            {
                int add = min(n-s, pos->count);
                s += add;
                pos->count -= add;
                money += add*pos->money;
                pos++;
            }
            send+=s;
 
            next.clear();
            for(pi i=pack.begin(); i!=pack.end(); i++)
            {
                if (i->count == 0) continue;
 
                i->money--;
                if (i->money == 0)
                {
                    lost += i->count;
                }
                else
                {
                    next.push_back(*i);
                }
            }
            pack.clear();
        }
 
        for(pi i = next.begin(); i!=next.end(); i++)
        {
            lost += i->count;
        }
        next.clear();
 
        cout << send << " " << lost << " " << money << endl;
    }
 
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2012, 09:10     Как работает эта программа?
Посмотрите здесь:

как работает эта программа(Алгоритм Рабина-Карпа с++)??? C++
Не понимаю как работает эта функция C++
C++ Эта программа безвредна?
C++ Как работает эта функция?
Как работает эта часть кода? C++
Как работает эта функция? Не могу никак разобраться! C++
C++ Не могли бы объяснить, как работает эта функция для удаления цифр?
C++ Как работает эта программа? (клиент-сервер)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 06:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru