P7680 [COCI2008-2009#5] JAGODA 题解

· · 题解

这道题使用的算法是“模拟”，是一道比较考思维的模拟题，根据题目来做即可

我就说几个坑点

  1. 统计需要的是在该天中所有放置过的杯子和火柴盒（之前题目翻译有误，详情见讨论区）
  2. 最后一组需要特判（因为最后一组可能不是完整的一组）
  3. 统计之前放置的时候，是需要计入之前的

更多详细思路见代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100010],b[100010];//a代表火柴盒 b代表杯子
int main(){
    cin>>n>>m;
    int bj=1;//该处的bj等同于题目中的k
    while(bj*bj<=n)bj++;
    bj--;
    /*
    为什么要减1呢？ 因为题目要求是k^2<=n的最大整数
    而我们上述代码求的是k^2>n的最小整数 所以减1即是题目所求
    */
    for(int i=0;i<m;i++){//枚举每一天
        int n1,n2,js=0;
        //n1代表该天购买的数量 n2代表得到第一个的兔子 js代表总共需要的火柴数量
        cin>>n1>>n2;
        for(int j=n2;j<=n1+n2-1;j++){//j枚举每一个可以得到的兔子
            if((j%bj==1&&j+bj-1<=n1+n2-1)||(j%bj==1&&j+bj-1>=n&&n==n1+n2-1)){
                /*
                第一种情况：（非末尾组）
                j%bj==1 代表第j只兔子是否为每个杯子的开头
                j+bj-1<=n1+n2-1 代表这个杯子的末尾是否超过我的草莓数量
                第二种情况：（末尾组）
                j%bj==1 代表第j只兔子是否为每个杯子的开头
                j+bj-1>=n 代表该组为末尾组
                n==n1+n2-1 代表该组最后一个也可以拿到草莓
                */
                b[j]++;//向杯子里放一根火柴
                js+=b[j];
                j+=bj;//直接跳到下一个杯子开头
                j--;
                //特别注意 这里需要减1抵消for循环的加1 （这里调了我好久QaQ）
            }
            else{
                a[j]++;//否则放到火柴盒里
                js+=a[j];
            }
        }
        cout<<js<<endl;
    }
    return 0;
}