[Small Coder Study Room] [NOI Online 2020-2 Beginner Group] Finished: Abominable precision will make you burnt

Minds

• It's a sad story when you're delusional about adding together several inexhaustible and rounded decimals to act as a distributive law, because the abominable precision will make you burnt...

label

• Greedy, binary search

topic address

• [NOI Online #2 Starter Group] not done
  • https://www.luogu.com.cn/problem/P6473

Title description

Input format

The three integers n, L, and v in the first line respectively represent the number of types of magic, the length of the hillside, and the speed of Sisyphus.

The second line contains n integers.The ith integer a_i represents the position of the ith magic effect.(1<i<n)

An integer q in the third line represents the number of queries from Zeus.

The next q lines contain an integer per line, and the integer t_i in line i represents the ith query from Zeus.(1<i<n)

Output format

Output q lines, each line has exactly one integer, and the integer in line i corresponds to the answer to the i-th query.(1≤i≤q)

If Zeus cannot make Sisyphus use more years than t_i anyway, output −1.

Sample input and output

Enter #1

3 6 33 5 141345

Output #1

012-1

Instructions/Tips

Solution

Little Coder Problem Solution 1

• One AC

void coder_solution() {// Improve the efficiency of cin and coutios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, l;double v;cin >> n >> l >> v;vector a(n);vector b(n);for(int i = 0; i < n; ++i) {cin >> a[i];}sort(a.begin(), a.end(), greater());b[0] = a[0] / v;for(int i = 1 ; i < n; ++i) {a[i] += a[i - 1];b[i] = a[i] / v;}int q, t;cin >> q;double T = l/v;int cnt;for(int i = 0; i < q; ++i) {cin >> t;if(T > t) {cout << 0 << endl;} else {cnt = upper_bound(b.begin(), b.end(), t - T) - b.begin();if (cnt >= n) {cout << -1 << endl;} else {cout << cnt + 1 << endl;}}}}