首页 > 其他分享 >花海(贪心)

花海(贪心)

时间:2024-11-11 19:30:45浏览次数:1  
标签:sort 花海 int sum cin long 贪心

using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        int b[n],g[m];
        long long sum=0;
        for(int i=0;i<n;i++){
            cin>>b[i];
            sum+=b[i]*m;
        }
        for(int i=0;i<m;i++){
            cin>>g[i];
        }
        
        sort(b,b+n);
        sort(g,g+m);
		//自己画图发现答案并不固定,但要总和最小所以要排序。找出最优解。 
        if(b[n-1]>g[0]){
        //如果某个男孩最少送出的花大于女孩最多收到的花。则不会出现这种情况。 
            cout<<"-1"<<"\n";;
        }else{
            if(b[n-1]==g[0]){
                for(int i=1;i<m;i++){
                    sum+=g[i]-b[n-1];
                    //如果g[i]-b[i]则不是最优解。 
                }
            }
            else{
                for(int i=1;i<m;i++){
                    sum+=g[i]-b[n-1];
                }
                sum+=g[0]-b[n-2];
            }
            cout<<sum<<"\n";
        }
    }
    return 0;
}
//1.排序方便找最优解,没想出来,直接做的下面的,也不对。 ```

标签:sort,花海,int,sum,cin,long,贪心
From: https://www.cnblogs.com/yue-mikasa/p/18540410

相关文章

  • 每周算法2:数学+模拟+哈希表+栈+线性dp+贪心(简单)
    目录1.统计数字描述输入描述:输出描述: 题解2.两个数组的交集(哈希表)描述题解 3.点击消除(栈)描述输入描述:输出描述: 题解4.牛牛的快递(模拟+补充)描述输入描述:输出描述:题解 5.最小花费爬楼梯(简单线性dp)描述输入描述:输出描述:示例1题解6.数组中两......
  • 带悔贪心 QOJ interval
    interval带反悔的贪心即通过堆(大根堆、小根堆)来维护当前贪心策略的最优解,若发现最优解不对,就退回上一步,更新最优解。将区间按照左端点排序,从左向右遍历区间。当前区间为\([l,r]\),取出当前右端点最左的区间,可以就匹配。如果不可以,去看看已经匹配的这些对区间中的\((b,c)\),\(c......
  • NOIP2024集训Day71 贪心
    NOIP2024集训Day71贪心B.[CCO2015]饥饿的狐狸显然的,要求出最大美味值,应该先交错吃温度最大的和最小的饼干。所以我们给所有饼干按照温度排序,交替选择左右端点吃,如果喝水能够达到更大那就先喝水再吃,反正水管够。分两种情况,即左右端点谁先开始,再取个\(\operatorname{max}\)。......
  • 【算法学习】反悔贪心
    前言反悔贪心,先选择局部最优,当不断向后更新时发现前面的决策在现在来看并不优就进行调整过去决策进行局部最优,可以说反悔贪心一步步扩宽自己的视野从而明白过去的错误。、如果动态规划是将各种削苹果的方式都展示出来的话,那反悔贪心就是削一下补回来一点再削。当然反悔贪心的题......
  • P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G:贪心
    [NOIP2004提高组]合并果子/[USACO06NOV]FenceRepairG题目描述在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的......
  • 算法设计与分析中的几个核心算法策略:动态规划、贪心算法、回溯算法和分治算法
    这些题目主要考察的是算法设计与分析中的几个核心算法策略:动态规划、贪心算法、回溯算法和分治算法。下面我将分别介绍这些知识点,并解析题目的详细解答过程。1.动态规划(DynamicProgramming,DP)知识点介绍:动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问......
  • 区间集合:高效解决无重叠区间问题【贪心、区间集合】
    无重叠区间问题的深入解析与C++实现题目理解在无重叠区间问题中,我们被给定一个区间集合intervals,其中每个区间以[start,end]的形式表示。我们的目标是确定最少需要移除多少个区间,以确保剩下的区间互不重叠。值得注意的是,当两个区间仅在一个点上接触时(例如[1,2]和[......
  • NOIP2024集训Day65 贪心
    NOIP2024集训Day65贪心A.[NOI2015]荷马史诗简化题意,即构造一颗\(k\)叉树,每个节点的权值为其所有孩子的权值之和,给定的\(n\)个数必须使用,其余空缺处用\(0\)补全。考虑使用优先队列,首先弹入\(n+(n-1)\%(k-1)\)个元素(不足处用0代替),然后每次弹出前\(k\)小的数......
  • 贪心
    原理通过证明局部最优解可以得出全局最优解,从而\(O(n)\)解决问题。常用数学归纳法证明贪心正确性。模板取\(x,y\),计算\(f(x\text{先于}y),f(y\text{先于}x)\),令\(f(x\text{先于}y)>f(y\text{先于}x)\),解出贪心公式。区间类区间覆盖选取尽量少的区间使得区间[s......
  • Day65 小贪心 & 自选杂题
    哎怎么必可公益赛被爆破了,怎么lifan还加了几道我们的训练题目作为补偿。CF不知道死了多久了,一上午都没有打成duel!今天上午精神状态明显好了很多,可能和咖啡有点关系吧。按照时间顺序写题吧。AT_arc070_b可以进行撤销背包,也可以算前后缀背包,都是记录方案数。不难的。AT_a......