首页 > 代码库 > codechef T3 计算器

codechef T3 计算器

CALC: 计算器
题目描述 大厨有一个计算器,计算器上有两个屏幕和两个按钮。初始时每个屏幕上显示的都是 0。没按 一次第一个按钮,就会让第一个屏幕上显示的数字加 1,同时消耗 1 单位的能量。 每按一次第二个按钮,会让第二个屏幕上显示的数字加上第一个屏幕上显示的数字,同时消 耗 B 单位的能量。 初始时,计算器有 N 单位的能量。大厨想知道在能量限制下,第二个屏幕上最大可以出现的 数字是多少?
输入格式
输入的第一行包含一个整数 T,代表测试数据的组数。接下来是 T 组数据。 每组数据仅有一行,包含两个整数 N 和 B。
输出格式
对于每组数据,输出一行,包含一个整数,代表所求的答案。
数据范围和子任务 ? 1 ≤ T ≤ 10,000 ? 1 ≤ N,B ≤ 1,000,000,000 子任务 1(20 分): ? 1 ≤ N,B ≤ 1,000
子任务 2(80 分): ? 无附加限制
样例数据
输入 3 10 2 8 5 6 1
输出 12 3 9
样例解释 对于第一组数据,可以使用 10 单位的能量,按一次第二个按钮耗费 2 单位的能量。大厨可以 按照下面的方案操作:

操作 屏幕一数字 屏幕二数字 剩余能量

按钮一 1 0 9

按钮一 2 0 8

按钮一 3 0 7

按钮一 4 0 6

按钮二 4 4 4

按钮二 4 8 2

按钮二 4 12 0

这就是道数学题 我们设操作二次数为x 那么结果就是x*(n-k*x)  x取值范围是x<n/k 定点是n/2k 所以顶点也就是最大值一定能取到 当然因为x一定是整数所以还得找一波左右比较一下就好啦233

技术分享
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<0||c>9){if(c==-) f=-1; c=getchar();}
    while(c>=0&&c<=9){ans=ans*10+(c-0); c=getchar();}
    return ans*f;
}
int T,n,k;
LL ans;
LL get_max(LL x){return x*(n-k*x);}
int main()
{
    T=read();
    while(T--){
        n=read(); k=read();
        int v1=n/(2*k),v2=v1+1;
        ans=max(get_max(v1),get_max(v2));
        printf("%lld\n",ans);
    }
    return 0;
}
View Code

 

codechef T3 计算器