Задача с сайта e-olymp.com.
Условие задачи
Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.
В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.
Входные данные
В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].
Выходные данные
Для каждого запроса с номером один выведите в отдельной строке количество человечков, поместившихся в шар.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 5 1 2 3 4 5 5 1 7 1 3 2 1 5 1 7 1 3 |
3 2 2 0 |
| 2 | 2 1 2 3 1 4 2 1 10 1 4 |
2 0 |
| 3 | 2 999999999 1000000000 4 1 999999999 2 1 1000000000 1 999999999 1 1000000000 |
1 0 1 |
Код на 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 |
#include <iostream> using namespace std; //Дерево отрезков. struct segment_tree{ long *tree; //Конструктор. segment_tree(int length){ tree = new long[4*length+1]; } //Построение дерева отрезков по массиву a. void build(int *a, int v, int tree_l, int tree_r){ if(tree_l == tree_r) tree[v] = a[tree_l]; else{ int tree_m = (tree_l + tree_r)/2; build(a, v*2, tree_l, tree_m); build(a, v*2+1, tree_m+1, tree_r); tree[v] = tree[v*2] + tree[v*2+1]; } } //Присваивание человечку на позиции pos веса new_val. void update(int v, int tree_l, int tree_r, int pos, int new_val){ if(tree_l == tree_r) tree[v] = new_val; else{ int tree_m = (tree_l + tree_r)/2; if(pos <= tree_m){ update(v*2, tree_l, tree_m, pos, new_val); } else{ update(v*2+1, tree_m+1, tree_r, pos, new_val); } tree[v] = tree[v*2] + tree[v*2+1]; } } //Нахождение количества поместившихся человечков. int find_numb_of_p(int v, int tree_l, int tree_r, int max_w){ if(tree_l == tree_r) return tree[v] <= max_w; int tree_m = (tree_l + tree_r)/2; if(tree[v*2] > max_w) return find_numb_of_p(v*2, tree_l, tree_m, max_w); else return tree_m - tree_l + 1 + find_numb_of_p(v*2+1, tree_m+1, tree_r, max_w-tree[v*2]); } }; int main() { int n, m, *weights; cin >> n; //Заполнение массива весов человечков. weights = new int[n+1]; for(int i = 1; i <= n; ++i){ cin >> weights[i]; } //Построение дерева отрезков. segment_tree tr(n); tr.build(weights, 1, 1, n); //Обработка запросов. cin >> m; int type, x, y, v; for(int i = 0; i < m; ++i){ cin >> type; if(type == 2){ cin >> x >> y; tr.update(1, 1, n, x, y); } else{ cin >> v; cout << tr.find_numb_of_p(1, 1, n, v) << '\n'; } } return 0; } |
Код на Java
|
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 |
import java.util.*; import java.io.*; //Для решения задачи требуется читать целые числа быстрее, чем это можно делать при помощи Scanner. class FastIntReader extends BufferedReader { int cur, res; FastIntReader(InputStream s){super(new InputStreamReader(s));} int getNextInt() throws IOException { cur = read(); res = 0; while(cur!=32 && cur!=-1 && cur != '\n'){ res*=10; res += (int)(cur-'0'); cur = read(); } return res; } } //Дерево отрезков. class SegmentTree { static long []tree; //Конструктор. SegmentTree(int length){tree = new long[4*length+1];} void build(int v, int treeL, int treeR, FastIntReader in) throws IOException { if(treeL == treeR) tree[v] = in.getNextInt(); else{ int treeM = (treeL + treeR)/2; build(v*2, treeL, treeM, in); build(v*2+1, treeM+1, treeR, in); tree[v] = tree[v*2] + tree[v*2+1]; } } //Присваивание человечку на позиции pos веса newVal. void update(int v, int treeL, int treeR, int pos, int newVal) { if(treeL == treeR) tree[v] = newVal; else{ int treeM = (treeL + treeR)/2; if(pos <= treeM){ update(v*2, treeL, treeM, pos, newVal); } else{ update(v*2+1, treeM+1, treeR, pos, newVal); } tree[v] = tree[v*2] + tree[v*2+1]; } } //Нахождение количества поместившихся человечков. int findNumberOfPeople(int v, int treeL, int treeR, long max_w) { if(treeL == treeR){ if(tree[v] <= max_w) return 1; else return 0; } int treeM = (treeL + treeR)/2; if(tree[v*2] > max_w) return findNumberOfPeople(v*2, treeL, treeM, max_w); else return treeM - treeL + 1 + findNumberOfPeople(v*2+1, treeM+1, treeR, max_w-tree[v*2]); } } class Main { public static void main (String[] args) throws java.lang.Exception { FastIntReader in = new FastIntReader(System.in); PrintWriter out = new PrintWriter(System.out); //Построение дерева отрезков. int n, m; n = in.getNextInt(); SegmentTree tr = new SegmentTree(n); tr.build(1, 1, n, in); //Обработка запросов. m = in.getNextInt(); int type, x, y, v; for(int i = 0; i < m; ++i){ type = in.getNextInt(); if(type == 2){ x = in.getNextInt(); y = in.getNextInt(); tr.update(1, 1, n, x, y); } else{ v = in.getNextInt(); out.print(tr.findNumberOfPeople(1, 1, n, v)); out.print('\n'); } } out.flush(); } } |
Описание
В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).
Код на ideone.com. (C++)
Засчитанное решение на e-olymp.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.com. (Java)
При решении задачи был использован материал с сайта e-maxx.ru.
Принято