Title: D. Ice Cream Balls
Title Link:/contest/1862/problem/D
Idea: dichotomize to find the case when all ice cream balls are of different types, assuming that the notation k, which satisfies k(k-1)/2 <=n ;This is not necessarily equal to k at this point, so consider that there are duplicate types of ice cream balls.
When there are two duplicate types of balls, the different types of ice cream that can be made are k(k-1)/2+1 , if there are three or more duplicate types of ice cream balls then the result is still plus 1 and the ice cream balls are wasted so the minimum number condition is not satisfied.
Therefore, the repeated types of ice cream balls end up being only n-k(k-1)/2;
Summarizing, the result is k+n-k(k-1)/2；
The detailed code is as follows:
Click to view code
#include <iostream>
#include <climits>
using namespace std;
#define ll long long
void solve(ll n)
{
ll l = 1, r = INT_MAX,ans=0;// 2147483647
while (l <= r)
{
ll mid = (l + r) >> 1;
if ((mid * (mid - 1) / 2) > n) r = mid - 1;
else
{
l = mid + 1;
ans = mid;
}
}
ll result = ans + n - (ans * (ans - 1) / 2);
cout << result << endl;
}
int main()
{
ios::sync_with_stdio(false);
(nullptr);
int t;
ll n;
cin >> t;
while (t--)
{
cin >> n;
solve(n);
}
return 0;
}