NC222478. [USACOJan2020B]Race
描述
输入描述
The first line will contain two integers K and N.
The next N lines each contain a single integer X.
输出描述
Output N lines, each containing a single integer for the minimum time Bessie needs to run K meters so that she finishes with a speed less than or equal to X.
示例1
输入:
10 5 1 2 3 4 5
输出:
6 5 5 4 4
说明:
When X=1, an optimal solution is:C++(g++ 7.5.0) 解法, 执行用时: 106ms, 内存消耗: 444K, 提交时间: 2023-03-04 20:32:01
#include <bits/stdc++.h>
#define int long long
#define cl(arr) memset(arr,0,sizeof arr)
using namespace std;
const int N=1e3+10;
int n,k,m,x,mx=10000000000;
string s,p;
int f[N],a[N];
void solve()
{
cin>>k>>n;
for(int i=1;i<=n;i++){
cin>>x;
for(int i=1;i*(i-1)<=2*k;i++){
if(i*(i-1)+i-min(i,x)*(min(i,x)-1)/2==k){
if(x>=i) {
cout<<i<<"\n";}
else cout<<2*i-x<<"\n";break;
}
if(i*(i-1)+i-min(i,x)*(min(i,x)-1)/2>k){
if(x>=i) {
cout<<i<<"\n";break;}
i--;
if(k-(i*(i-1)+i-x*(x-1)/2)<i){
cout<<2*i-x+1<<"\n";
}
else{
if((k-(i*(i-1)+i-x*(x-1)/2))%i==0) cout<<2*i-x+(k-(i*(i-1)+i-x*(x-1)/2))/i<<"\n";
else cout<<2*i-x+1+(k-(i*(i-1)+i-x*(x-1)/2))/i<<"\n";
}
break;
}
}}
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
// for(auto i :"abcdefg") cout<<i<<"\n";
// cin>>t;
t=1;
while(t--)
solve();
return 0;
}
/*
4 3 2 3
2 2 1 1 2
*/
C++(clang++ 11.0.1) 解法, 执行用时: 55ms, 内存消耗: 440K, 提交时间: 2023-03-30 21:15:56
#include<iostream>
using namespace std;
int main()
{
int n,k;
cin>> k >> n;
for (int i = 0; i < n;i++){
int x, left = 0, right = 0, time = 0;
cin >> x;
for (int v = 1; v; v++){
left += v;
time++;
if((left + right) >= k){
break;
}
if (v >= x) {
right += v;
time++;
if ((left + right) >= k){
break;
}
}
}
cout<< time << endl;
}
return 0;
}