Thảo luậnSnackDown Online Qualifier 2017 - Snake Eating

Chef vừa mua rất nhiều rắn và những con rắn này đang rất đói nên đang ăn thịt lẫn nhau. Mỗi con rắn thứ i có chiều dài là Li, bạn đã biết chiều dài ban đầu của nó. Một con rắn có thể ăn bất cứ con rắn nào không dài hơn nó. Ví dụ, một con rắn i sẽ có thể ăn một con rắn j (i ≠ j), nếu Li ≥ Lj. Và khi một con rắn ăn một con rắn khác, chiều dài của nó sẽ tăng lên 1. Tức là Li tăng thêm 1.

Chef không để ý về việc các con rắn đang ăn thịt nhau. Tất cả những gì anh ấy muốn là có càng nhiều rắn càng tốt mà chiều dài ít nhất phải bằng một giá trị cụ thể. Bạn được cho Q giá trị K1, K2, .., KQ. Hãy in ra câu trả lời độc lập đối với từng giá trị. Cụ thể, với mỗi Ki, giả sử rằng bạn bắt đầu từ đầu với tất cả các con rắn còn sống và chiều dài như các giá trị ban đầu được đưa ra trong dữ liệu đầu vào và bạn phải tìm ra số rắn lớn nhất mà chiều dài của mỗi con rắn đó ít nhất bằng Ki.

Dữ liệu vào

- Dòng đầu tiên chứa một số nguyên T – số test. Các test được miêu tả như sau:

- Dòng đầu tiên của mỗi test chứa hai số nguyên N và Q lần lượt là số rắn ban dầu và số lượng truy vấn.

- Dòng thứ hai của mỗi test chứa N số nguyên L1, L2, .., LN, thể hiện chiều dài ban đầu của các con rắn.

- Dòng thứ i trong Q dòng tiếp theo chứa một số nguyên duy nhất là Ki.

Dữ liệu ra

- Ở mỗi test, in ra Q dòng, dòng thứ i có một số nguyên duy nhất: số lượng rắn nhiều nhất mà Chef có với chiều dài mỗi con ít nhất bằng Ki.

Ràng buộc

- 1 ≤ T ≤ 5

- 1 ≤ N, Q ≤ 10^5

- 1 ≤ Li ≤ 10^9

- 1 ≤ Ki ≤ 10^9

Ví dụ

Input:

2
5 2
21 9 5 8 10
10
15
5 1
1 2 3 4 5
100

Output:

3
1
0

Giải thích

Trong test đầu tiên, truy vấn thứ nhất, con rắn thứ hai (độ dài 9) có thể ăn con rắn thứ tư (độ dài 8), do đó chiều dài sau đó của nó là 10. Bây giờ, có 4 con rắn còn lại, và chiều dài của chúng là {21, 10, 5, 10}. Do đó, chúng ta có ba con rắn với chiều dài ≥ 10: hai con trong số chúng có chiều dài là 10 và một con dài 21. Đây là cách tốt nhất bạn có thể làm.

Ở truy vấn thứ hai, bất luận điều gì xảy ra, bạn cũng không thể có nhiều hơn một con rắn có chiều dài là 15.

Trong test thứ hai, bất luận điều gì xảy ra, bạn cũng không thể có bất cứ con rắn nào có chiều dài ≥ 100. Do đó câu trả lời là 0.

____________

Time Limit: 2 secs

Source Limit: 50000 Bytes

Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

Chả hiểu, và nó là gì v??

Viết code theo yêu cầu =))

Viết đê

Viết rồi, test OK rồi =))

Share đê

Code bị limit. Pro fix hộ

Code C++:

#include<bits/stdc++.h>
  using namespace std;
int t, n, q, k;
int main() {
  cin >> t;
  for (int a = 0; a < t; a++) {
    cin >> n;
    cin >> q;
    int l[n];
    for (int b = 0; b < n; b++) {
        cin >> l[b];
    }
    sort(l, l+n, greater<int>());
    for (int c = 0; c < q; c++) {
        cin >> k;
        int r = 0;
        if (l[0] + n - 1 < k) {
            cout << "0\n";
            break;
        }
        int p = n;
        for (int c = 0; c < p; c++) {
            if (l[c] >= k) {
                r++;
            } else {
                if (l[c] + p - c - 1 >= k) {
                    r++;
                    p = p - (k - l[c]);
                } else {
                    break;
                }
            }
        }
        cout << r << "\n";
    }
  }
  return 0;
}