首页 > 其他分享 >P5963 [BalticOI ?] Card 卡牌游戏【来源请求】

P5963 [BalticOI ?] Card 卡牌游戏【来源请求】

时间:2024-01-25 10:22:50浏览次数:21  
标签:node int sum 卡牌 BalticOI P5963 ###


[rt](https://www.luogu.com.cn/problem/P5963)
------------
## part1
### 题意简述
给你 $n$ 张纸牌,每张纸牌有两个面。
将 $n$ 张纸牌按一定顺序填入框中。填入卡牌时,不一定需要按照卡牌和框的顺序进行填写(即可以进行位置的调换)。求在一定顺序下式子最小的结果。
### 思路
因为格式是按减和加来回变化的,所以要加的数有 $n/2$ 个,减的也有 $n/2$ 个。因为要结果最小,所以尽量使 $sum_i$ 较大的 $A_i$ 所以得到贪心策略:取卡牌 $sum$ 值大的一半的 $A_i$,放在减号框内,$sum$ 值小的一半的 $B_i$ 放在加号框内,此时的结果最小。
### so
定义一个 $sum_i$ 来存放 $x_i+y_i$ 的值。按 $sum_i$ 排序。选前 $n/2$ 个放入加号框,后 $n/2$ 放入减号框。
## part2
最后直接上代码。
### code
```
#include<bits/stdc++.h>
#define int long long
int n,ans=0;struct node{int a,b;}c[50000009];
int cmp(node x,node y){if((x.a+x.b)<(y.a+y.b)){return 1;}return 0;}
using namespace std;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>c[i].a>>c[i].b;
sort(c+1,c+1+n,cmp);
for(int i=1;i<=n/2;i++) ans+=min(c[i].a,c[i].b);
for(int i=n/2+1;i<=n;i++) ans-=max(c[i].a,c[i].b);
cout<<ans;
return 0;
}
```

## End
另附上一则温馨提示 $n\leq 5\cdot 10^5$ 且 $|A_i|,|B_i|\leq 10^7$。

标签:node,int,sum,卡牌,BalticOI,P5963,###
From: https://www.cnblogs.com/wenzhihao2023/p/17986444

相关文章

  • 题解 P6226 [BalticOI 2019 Day1] 潜艇
    【洛谷博客】题解P6226[BalticOI2019Day1]潜艇题意很清楚,忽略。分析看到这种字符串题很容易想到直接广度优先搜索,复杂度\(O(rc4^m)\)。很显然承受不了,所以考虑DP。状态设计设\(f_{i,x,y}\)表示执行完前\(i\)个操作后位置\((x,y)\)能否作为终点。设命令字符......
  • P4331 [BalticOI 2004] Sequence 数字序列
    [BalticOI2004]Sequence数字序列LuoguP4331题目描述给定一个整数序列\(a_1,a_2,\cdots,a_n\),求出一个递增序列\(b_1<b_2<···<b_n\),使得序列\(a_i\)和\(b_i\)的各项之差的绝对值之和\(|a_1-b_1|+|a_2-b_2|+\cdots+|a_n-b_n|\)最小。【数......
  • [BalticOI 2019 Day2] 汤姆的餐厅
    [BalticOI2019Day2]汤姆的餐厅题目背景译自BalticOI2019Day2T1.Tom'sKitchen题目描述Tom'sKitchen是一家非常受欢迎的餐厅,其受欢迎的原因之一是每份菜都由至少$K$名厨师进行准备。今天有$N$份菜需要准备,第$i$份菜的准备时间是$A_i$小时。Tom可以......
  • P7514 [省选联考 2021 A/B 卷] 卡牌游戏
    [省选联考2021A/B卷]卡牌游戏题目描述Alice有\(n\)张卡牌,第\(i\)(\(1\lei\len\))张卡牌的正面有数字\(a_i\),背面有数字\(b_i\),初始时所有卡牌正面朝上。现在Alice可以将不超过\(m\)张卡牌翻面,即由正面朝上改为背面朝上。Alice的目标是让最终朝上的\(n\)个数......
  • 【题解】BalticOI 2009 Day1 - 甲虫
    BalticOI2009Day1-甲虫https://www.luogu.com.cn/problem/P4870首先看到题面就能想到排序后区间dp。设\(f_{i,j,0/1}\)表示区间\([i,j]\),收集完毕后在哪个端点时能收集到最多的露水,但是发现转移过程中还需要这时的最小时间。如果再添加一个数组维护这时的最小时间呢?那......
  • P4678 [BalticOI 2005] Bus Trip 题解
    P4678[BalticOI2005]BusTrip题解(RE:题解再改造!!)贴码#include<bits/stdc++.h>#defineMAXN500010usingnamespacestd;//ifstreamis("trip.in",ios::in);//ofstreamos("trip.out",ios::out);//#definecinis//#definecoutosintn,m,p,t,tote......
  • LuoguP7637 [BalticOI 2006 Day 1] BITWISE EXPRESSIONS
    题目大意给定\(N\)对数据,每对数据包含两个整数\(A_i\)和\(B_i\),表示这一对数据的\(v_i\)的范围:\(A_i\leqv_i\leqB_i\)。又将这\(N\)对数据分为\(P\)组,其中\(K_i\)表示第\(i\)组数据中有多少对数据。我们设第\(i\)组数据中将所有数按位与的结果为\(X_i\),求......
  • 【算法】用c#实现德州扑克卡牌游戏规则
    德州扑克是一种牌类游戏,可多人参与,它的玩法是,玩家每人发两张底牌,桌面依次发5张公共牌,玩家用自己的两张底牌和5张公共牌自由组合,按大小决定胜负。使用c#完成功能Hand()以返回手牌类型和按重要性递减顺序排列的等级列表,用于与同类型的其他手牌进行比较,即最佳手牌。可能的手牌按价......
  • P4795 [BalticOI 2018] 基因工程 题解
    题目传送门:Click。蒟蒻看见这道题,想了足足一个小时,过后顿有所悟,故作此篇。首先,看到题目,光是数据就已经达到了\(\operatorname{O}(nm)\)的级别,再看一看数据范围:\(3\leqn,m\leq4,100\)。显然是一道时间复杂度为\(\operatorname{O}(n,m)\)级别的题目。本蒟蒻首先观察了样......
  • 950. 按递增顺序显示卡牌 (Medium)
    问题描述950.按递增顺序显示卡牌(Medium)牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。最初,这些卡牌在牌组里是正面朝下的(即,未显示状态)。现在,重复执行以下步骤,直到显示所有卡牌为止:从牌组顶部抽一张牌,显示它,然后将其从牌组中移出。......