1🐋🐋🐋银行账户（黄金；模拟）

时间限制：1秒

占用内存：128M

🐟题目描述

据说对银行账户进行盗窃时，如果只盗取小数点下的数值，就不容易引起注意，所以你决定进行尝试。

银行总共有n个账户，m次转账，对每次转账，你可以盗取（转账金额-转账金额下取整）的资金，并使转入账户的警戒值增加相同数值，当任意账户的警戒值>1，或者无法实现转账 (转出账户余额不足)，或者m次转账全部完成，你停止盗取，请计算总盗取金额。

🐟输入输出格式

输入格式：
第一行n，m，表示有n个账户，m条转账记录；
第二行n个实数，表示每个账户的资金；
接下来m行，每行有三个参数；
整数x，整数y，实数z，分别表示转出账户，转入账户，和转账金额。
​
输出格式：
输出盗取金额,保留两位小数。

🐟样例

🐚样例1

输入：
5 5
2 2 2 2 2
1 2 1.5
2 1 1.5
1 2 1.5
2 1 1.5
1 2 1.5
​
输出：
2.00

🐚备注

1≤n≤1000,1≤m≤10000；
0<每个账户初始资金<100<每个账户初始资金<10；
1≤x,y≤n,x≠y；
0<z<100；
样例解释：
第一次转账后：0.5 3 2 2 2，已盗取金额 0.5，账户 2 警戒值 0.5；
第二次：1.5 1.5 2 2 2，已盗取 1，账户 1 警戒值 0.5；
第三次：0 2.5 2 2 2，已盗取 1.5，账户 2 警戒值 1；
第四次：1 1 2 2 2，已盗取 2，账户 1 警戒值 1；
第五次，账户 1 余额不足，转账无法进行，停止。 

🐟题目思路

这道题目不难，就是模拟，这里主要是记录一下一些在这个题目中出现的之前不会的函数：

🌮取整、截取等操作

以下函数都是<cmath>中的函数

//floor()： 取不大于参数的最大整数值（向下取整）。
#include <cmath>
double result = floor(3.14);  // result = 3.0
​
//ceil()： 取不小于参数的最小整数值（向上取整）。
#include <cmath>
double result = ceil(3.14);   // result = 4.0
​
//round()： 四舍五入到最接近的整数值。
#include <cmath>
double result = round(3.14);  // result = 3.0
​
//trunc()： 截取小数部分，返回整数部分。
#include <cmath>
double result = trunc(3.14);  // result = 3.0
​
//fmod()： 返回参数1除以参数2的余数。
#include <cmath>
double result = fmod(5.7, 3.2);  // result = 2.5

🌮控制输出小数位数

#include <iostream>
#include <iomanip>
​
int main() {
    double number = 3.14159265359;
​
    // 设置输出格式，保留两位小数
    cout << std::fixed << std::setprecision(2) << number << endl;
​
    return 0;
}

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
double a[1010][2];
​
int main( )
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i][0];
        a[i][1]=0;
    }
    int l,r;
    double change;
    double ans=0;
    for(int i=0;i<m;i++)
    {
        cin>>l>>r>>change;
        if(a[l][0]<change)
        {
            cout<<std::fixed<<std::setprecision(2)<<ans<<endl;
            return 0;
        }
        double res=floor(change); 
        a[l][0]-=change; 
        a[r][0]+=res;
        res=change-res;//变成小数部分
        a[r][1]+=res;
        ans+=res;
        if(a[r][1]>1)
        {
            cout<<std::fixed<<std::setprecision(2)<<ans<<endl;
            return 0;
        }
    }
    cout<<std::fixed<<std::setprecision(2)<<ans<<endl;
    return 0;
}

2🐋🐋🐋任务分配（星耀；二分）

时间限制：1秒

占用内存：128M

🐟题目描述

小码哥在一个项目组里担任组长，如今小码哥的负责的项目ddl就要到了，为了能够尽快完成项目，小码哥需要合理的安排任务给组员，以保证最快完成这个项目，但由于各个任务之间存在一定的联系性，因此给组员分配的任务必须是相邻的（即不能给组员分配第一号、第三号和第四号这种不相邻的任务）。但是由于还需要人手去负责另外的事情，因此小码哥还想要让一些人的任务在前面的基础上尽可能的少，小码哥决定让做前面的任务的人的任务少一点（能把前面的人的任务分配给后面相邻的人而不会增加整个项目完成时间的情况下，优先分配给后面的人）。

请你给出一个方案满足小码哥的要求。

🐟输入输出格式

输入格式：
第一行两个整数t，k，t为任务数，k为组员数；
第二行t个整数，第i个整数表示完成第i个任务所需的时间。
​
输出格式：
输出k行，每行两个整数，第i行的两个数分别表示第i个组员负责的任务的起始编号和结束编号，输出按照起始编号从小到大排序（如果第i个人没任务则第i行输出0）。

🐟样例

🐚样例1

输入：
5 4
2 3 2 2 6
​
输出：
0 0
1 2
3 4
5 5

🐚备注

其中：1≤k≤t≤10000，所有单个任务所需时间<10000

🐟题目思路

提取题目关键词：

• 任务均分给所有人

• 每个人完成任务的总用时最少

• 先分配给后边的人

根据关键词分析：

• 均分给所有人且用时最少：需要找到一个数mid满足所有的任务可以被切成<=mid的块

  • 每块任务总用时可能的范围：l，只有1个任务，那就是用时最少的任务；r，有所有任务，那就是所有任务的用时总和

  • 使用二分法找到满足条件的mid

• 先分配给后边的人：从后往前逆序分配任务

  • 使用数组记录每个任务会被分给谁，然后从前往后遍历这个数组输出即可

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
int t,k,a[10010],sum[10010],minm=INT_MAX;
//a[i]用来记录所有任务的用时，sum[i]用来记录所有任务的前缀和，minm用来找到用时最短的任务用时
bool check(int mid)//用来判断mid可否满足将所有任务划分成每块mid大小且块数小于等于人数
{
    int c=0,num=0;//c用来标记任务块数
    for(int i=1;i<=t;i++)//遍历所有任务，将任务分成用时<=mid的一块块
    {
        if(num+a[i]>mid)//加上这个任务就超出mid了，那这一块分配结束
        {
            c++;
            num=0;
        }
        num+=a[i];
        if(num>mid) return false;//这表示，无法将所有任务按要求分成每一块<=mid的情况，此mid不合适
    }
    if(num!=0) c++;
    return c<=k;//最后判断分成的块数是否超过人数，超过人数就完成不了了
}
​
int main( )
{
    cin>>t>>k;
    for(int i=1;i<=t;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];//计算所有任务前缀和
        minm=min(minm,a[i]);//找到用时最短任务的用时
    }
    //二分查找，找到分配任务的最小时间ans
    int l=minm,r=sum[t],ans=sum[t];
    //2，5，7，9，15
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))//这说明每个人分到mid数量的任务是可行的，去左半部分继续查看找到最短用时
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;//这说明每个人分到mid数量的任务，任务还完不成，说明每个人要做多于mid的任务，去右半部分找
    }
    //cout<<ans<<endl;//
    int c=k,num=0;
    int f[10010];//用来记录某个任务是属于哪一个人（块）的
    for(int i=t;i>=0;i--)//倒着来分配任务
    {
        if(num+a[i]>ans)//将任务从后往前切分成<=ans大小的块
        {
            c--;
            num=0;
        }
        num+=a[i];
        f[i]=c;
    }
    if(f[1]!=0)//这说明任务分配完了，但是前f[1]个人还没有分到任务
    {
        for(int i=1;i<f[1];i++) cout<<0<<" "<<0<<endl;
    }
    cout<<1<<" ";
    for(int i=1;i<t;i++)
    {
        if(f[i]!=f[i+1]) cout<<i<<endl<<i+1<<" ";
    }
    cout<<t<<endl;
    return 0;
}

3🐋🐋🐋拦截罪犯（钻石；二分）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例1

🐚备注

🐟题目描述

同样的思路，使用二分法搜索最小疏漏距离，具体详见代码注释。

🐟代码

#include<bits/stdc++.h>
​
using namespace std;
const int N=1e5+7;
int L,n,k,a[N],l,r,mid,ans;
​
bool check(int p)//给一个距离p
{
    int c=0;
    for(int i=2;i<=n;i++)
    {
        int temp=a[i]-a[i-1];//得到当前相邻两个警察之间的距离
        int a1=temp/p,a2=temp%p;//a1表示当前距离能放下几组距离为p的警察，a2表示当前距离放下这几组距离为p的警察后还剩的小距离
        if(a1)//如果以p为区间可以在该区间放下至少1组警察 
        {
            //这里是为了避免尾端重复放置警察的问题
            if(a2) c+=a1;
            else c+=a1-1;
        }
    }
    if(c>k) return false;//这表示，新放入的警察间距离为p时，k组不够放
    else return true;
}
​
int main()
{
    cin>>L>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    //二分，查找最小新放入的警察间距离
    l=1,r=L;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid)) //距离为mid时满足条件，继续找最小距离
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

4🐋🐋🐋召唤神龙（钻石；二分）

时间限制：2秒

占用内存：512M

🐟题目描述

小码哥有n种卡，第i种卡的数目为c[i]。另外有一种特殊的卡：烛龙卡，简称r卡。它的数目是m。可以用每种卡各一张来组成一套卡，也可以用一张r卡和除了某一种卡以外的其他卡各一张组成1套卡，这样就可以召唤神龙，一套卡可以召唤一只神龙。比如，当n=3时，一共有4种合法的套卡：{1,2,3}, {r,2,3}, {1,r,3}, {1,2,r}。 给出n，m和c[i]，现在小码哥需要组成尽量多的套卡。每张卡最多只能用在一副套卡里（可以有卡不使用）。

🐟输入输出格式

输入格式：
第一行包含两个整数n，m，即卡的种数和烛龙卡的个数；
第二行包含n个整数c[i]，即每种牌的张数。
​
输出格式：
输出仅一个整数，最大召唤神龙条数。

🐟样例

🐚样例1

输入：
4 5
2 3 4 5
​
输出：
4

🐚备注

50%的数据满足：2≤n≤5,0≤m≤10^6,0≤c[i]≤200；
100%的数据满足：2≤n≤50,0≤m,c[i]≤500,000,000。

🐟题目描述

这里使用逆向思路，正向思路是用一张牌就减一张，我们这里逆向来想，既然r卡可以和其他n-1张卡组合，那我们就可以把r卡看作万能卡，可以变成任何卡，我们就把这m张卡尽量均衡地补到那些少的卡的种类中，只有尽量均衡才能让组数最多（最优的情况是所有种的卡都一样多，这样就一张也不浪费了）。

• 这里使用最大堆（queue），每次m减少都将最少数量的卡（top）的数量加一

除了尽量均衡外，还有一个需要注意的点，就是m可能还没有补完，剩下的数字卡就已经无法再组成一套牌了。

• 这里就是while的结束条件：ans>p.top( )。一共n种卡，有一张卡的数量少于ans那么就组不成ans组套牌了，所以这就是结束条件，并且结束时ans一定比p.top( )大一。那么此时p.top( )就是答案了。

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
​
int main( )
{
    int n,m,temp;//n种卡和m张r卡
    cin>>n>>m;
    priority_queue<int,vector<int>,greater<int> > p;//最大堆，O(logn)
    for(int i=0;i<n;i++)
    {
        cin>>temp;//输入每种牌的张数
        p.push(temp);
    }
    int ans=0;
    //任意n张不同的牌组合即可
    while(ans<=p.top())//ans>p.top()的时候结束，如果此时m还没用完，就不用填了，因为现在的各卡牌数量已经无法生成ans（更多）组了；如果m用完了，就表明现在的普通卡的各卡牌数量已经无法生成ans（更多）组了
    {
        ans++;
        if(m)//用r卡去尽量均衡地填数量少的那些牌
        {
            int minm=p.top();
            p.pop();
            p.push(minm+1);
            m--;
        }
    }
    cout<<p.top()<<endl;
    return 0;
}

5🐋🐋🐋异或和的或（星耀；前缀和；贪心）

🐟题目描述

小码哥在编写新程序的时候遇到了这样一个难题：现在有一个长度为n的整数序列，我们可以将这个序列任意划分成m段连续区间，设每个区间内数字的异或和为ei，求e1 or e2 or e3…or em的最小值。

🐟输入输出格式

输入格式：
第一行，两个整数n，m；
第二行，n个整数 a1,a2,a3,…an。
​
输出格式：
一行一个整数：表示所求得的最小值。

🐟样例

🐚样例1

输入：
3 2
1 5 6
​
输出：
3

🐚备注

对于 100% 的数据，1≤m<n≤5×105，0≤ai≤10^18。

🐟题目思路

这一道题目有点绕，建议大家直接看视频学习一下思路，这里我就简单写一下我能理解的部分：

MT3019 异或和的或_哔哩哔哩_bilibili

这道题目用了前缀和、贪心思想。

这里主要有几个点：

• 输入a[i]是顺道求出前i个数的异或和

• 从最高位向最低位遍历判断每位能否为0

• a[n]表示前n个数的异或和值，那么某位为0，就说明其中一定有几个段也都为0，找出这些段，如果这些段的数量满足大于等于m，那么这样分就是可以的，这些位的后边也就都不用再考虑动他们划分成其他情况了，所以标记为1

• 那么对于a[n]为1的某位，一定会至少有一个区间的该位置为1，那么答案的这个位置就标为1（这里我有点不太懂）

• 如果a[n]的某位为0但是划分的段数小于m，那么答案的这个位置也标为1（这里我也有点不太懂）

欢迎懂的大佬们评论区教一下，谢谢🌹🌹🌹~

🐟代码

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
ll a[500001]={0},ans;
int vis[500010]={0};//该数组用来标记某一位是否被访问过
int m,n;
​
//或，只要某个位为1，就是1
//要保证最小，那么高位要尽可能是0
​
int main( )
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]^=a[i-1];//计算前缀异或和
    }
    //找最小异或和
    for(int i=60;i>=0;i--)//从最高位遍历二进制位，10^18的二进制表示共有60位
    {
        int c=0;
        for(int j=1;j<=n;j++)//统计数组a中未被访问过且该位为0的数字个数
        {
            if(!vis[j]&&(a[j]&(1ll<<i))==0) c++;//数组a中第j个元素的第i位是否为0，数0的分割点
        }
        if((a[n]&(1ll<<i))==0&&c>=m)//如果数组a中所有数字在当前位i上的异或和为0并且满足划分的段数要求，则将这些位置标记为已访问
        {
            //大于等于m，这说明可以满足划分成m段是，这些的段前i位都为0，那么或也就都是0
            for(int j=1;j<=n;j++)
            {
                if(a[j]&(1ll<<i)) vis[j]=1;//置为1是为了防止遍历其他位时的贪心分割方案将该点换了，如果这样的话，就不能保证前边这位是0了
            }
        }
        else ans|=(1ll<<i);
        //如果当前位为1，那么无论如何划分，该位都会被包含在某个区间中，为了尽可能减小异或和，我们就将该位设为1
        //如果当前位为0，并且划分的段数不足以覆盖所有当前位为0的数字，那么无法保证每个区间的异或和最小。在这种情况下，为了满足划分的要求，我们不得不将该位设为1，以便在划分区间时能够包含足够的当前位为0的数字
    }
    cout<<ans<<endl;
    return 0;
}

🥗欢迎大佬们在评论区不吝赐教，有问题我们评论区见~

⭐点赞收藏不迷路~