卖萌型选手

NC21774. 卖萌型选手

描述

鸡尾酒在一场cf的div2比赛中被血虐，一道简单大模拟竟然一个半小时都没AC，认清自己的实力之后他选择做一名卖萌型选手。有一天鸡尾酒遇到了一个炒鸡喜欢的小姐姐，喜欢就要行动，藏着掖着是没有结果的！所以他决定通过自己最擅长的方式——卖萌，来获得小姐姐的芳心。
赤耳对鸡尾酒说：我也会嘤嘤嘤可是还是单身，卖萌不一定有用吧？

鸡尾酒说：没有卖萌解决不了的问题，如果有，那说明你表现的还不够萌！而且卖萌不是光在键盘上嘤嘤嘤QAQ，而是要有自己的特色。一般人卖萌都会使自己的可爱度增加一个普通数字，但是我的卖萌更立体，所以我每次能让自己的可爱度增加一个平方数！

_______________________________

初始鸡尾酒的可爱度为0，他每一次卖萌都会使可爱度增加i²。初始i=1，每次卖萌之后鸡尾酒都会对卖萌有新的理解，能得到的可爱度就会更多，所以每次卖萌之后i=i+1（第二次增加2²,第三次3²……）

在数次卖萌之后，如果鸡尾酒的总可爱度不大于k，则小姐姐对鸡尾酒的好感度等于鸡尾酒的可爱度。

但是如果鸡尾酒的可爱度超过k，小姐姐则会认为鸡尾酒是一个只会卖萌的软蛋，好感度变为-1。

鸡尾酒想请你帮他算算，他最多能获得小姐姐的好感度是多少。

输入描述

输入第一行包含一个整数T(T<=200000)，表示T组测试数据，
每组数据包含一个整数k(0<=k<=10¹⁸)，代表小姐姐的忍耐上限

输出描述

输出T行，每行包含一个整数

代表鸡尾酒能达到的最高好感度。

示例1

输入:

输出:

1
1
5

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 170ms, 内存消耗: 4996K, 提交时间: 2019-11-12 19:50:07

#include<stdio.h>
#include<math.h>
int main()
{
	long long n;
	scanf("%lld",&n);
	while(n--)
	{
	long long t,m,i,sum;
		t=sum=0;
		scanf("%lld",&m);
		i=pow(3*m,1.0/3)-1;
		t=sum=i*(i+1)*(2*i+1)/6;
        i++;
		while(sum<=m)
		{
			t=sum;
			sum=sum+i*i;
			i++; 
		}
		printf("%lld\n",t);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 218ms, 内存消耗: 27368K, 提交时间: 2018-12-22 17:26:38

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+5;
ll a[N];
int main(){
	int T;
	cin>>T;
	for(int i=1;i<=N-5;i++){
		a[i]=a[i-1]+1ll*i*i;
	}
	while(T--){
		ll x;
		scanf("%lld",&x);
		int t=lower_bound(a+1,a+1+N,x)-a;
		if(a[t]>x)t--;
		printf("%lld\n",a[t]);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 137ms, 内存消耗: 7260K, 提交时间: 2018-12-23 12:55:30

#include <stdio.h>
#include <math.h>
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		long long int k,s,i,j,n;
		scanf("%lld",&k);
		s=n=0;
		i=pow(3*k,1.0/3)-1;
		s=n=i*(i+1)*(2*i+1)/6;
		i++;
		while(n<=k){
			s=n;
			n=n+i*i;
			i++;
		}
		printf("%lld\n",s);
	}
	return 0;
}