NOIP模拟分糖果（贪心）

灰太狼 2021-11-26 07:22 342阅读 0赞

# [就是这道题][Link 1] #

# 【题目分析】 #

竟然又是一道氵谷原题。。。。。。。

关于排序的正确性以及正确的排序见[这篇博客][Link 2]

# 【代码~】 #

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int MAXN=5e4+10;
    
    int T,n;
    struct student{
    	LL a,b,c,x;
    	friend inline bool operator<(const student &a,const student &b){
    		if(a.x!=b.x)
    		  return a.x<b.x;
    		if(a.x<=0)
    		  return a.a<b.a;
    		return a.b>b.b;
    	}
    }stu[MAXN];
    LL ans;
    
    int Read(){
    	int i=0,f=1;
    	char c;
    	for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
    	if(c=='-')
    	  f=-1,c=getchar();
    	for(;c>='0'&&c<='9';c=getchar())
    	  i=(i<<3)+(i<<1)+c-'0';
    	return i*f;
    }
    
    int main(){
    	T=Read();
    	while(T--){
    		n=Read();
    		for(int i=1;i<=n;++i){
    			stu[i].a=Read(),stu[i].b=Read();
    			if(stu[i].a>stu[i].b)
    			  stu[i].x=1;
    			else{
    				if(stu[i].a<stu[i].b)
    				  stu[i].x=-1;
    				else
    				  stu[i].x=0;
    			}
    		}
    		sort(stu+1,stu+n+1);
    		for(int i=1;i<=n;++i){
    			stu[i].a+=stu[i-1].a;
    			stu[i].c=max(stu[i-1].c,stu[i].a)+stu[i].b;
    		}
    		cout<<stu[n].c<<'\n';
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/Ishtar/p/10010711.html

[Link 1]: https://www.luogu.org/problemnew/show/P2123
[Link 2]: https://www.luogu.org/blog/liuzibujian/solution-p2123

发表评论取消回复

表情：

评论列表（有 0 条评论，342人围观）

还没有评论，来说两句吧...

相关阅读

相关 NOIP模拟34

考试的时候被T2卡了一年。。。。考虑了一下正解的式子，然后没去给左边分解因数，去给后面乘倍数。。。理论复杂度O（n^2），实际好像卡不掉的样子。但是由于我智障的打了一棵主席树，

川长思鸟来/ 2023年08月17日 16:48/ 0 赞/ 132 阅读

相关贪心算法之分糖果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

刺骨的言语ヽ痛彻心扉/ 2023年01月02日 12:27/ 0 赞/ 208 阅读

相关 leetcode 135. Candy 分糖果 + 很经典的贪心算法

There are N children standing in a line. Each child is assigned a rating value. You are

旧城等待，/ 2022年06月08日 05:59/ 0 赞/ 259 阅读

相关分糖果

问题描述　　有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：　　每个小朋友都把自己的糖果分一半给左手边的孩子

叁歲伎倆/ 2022年05月28日 02:10/ 0 赞/ 279 阅读

相关 NOIP 2002 均分纸牌(贪心||模拟)

题目描述有N堆纸牌，编号分别为1，2，...，N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1的堆上取的纸牌，

我不是女神ヾ/ 2022年05月17日 12:25/ 0 赞/ 435 阅读

相关【数据结构】贪心算法（人民币、分糖果）

【0】目录一、贪心算法存于生活中 1.1人民币支付问题 1.1.1算法思想 1.1.2程序实现 1.1.3程序结果 1、举个实例二、分糖果 l

分手后的思念是犯贱/ 2022年05月16日 00:39/ 0 赞/ 302 阅读

相关分糖果

题目描述：有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：每个小朋友都把自己的糖果分一半给左手边的孩子。一轮分糖后，拥有奇数颗糖的孩子由

太过爱你忘了你带给我的痛/ 2022年03月16日 12:10/ 0 赞/ 324 阅读

相关 NOIP模拟分糖果（贪心）

[就是这道题][Link 1] 【题目分析】竟然又是一道氵谷原题。。。。。。。关于排序的正确性以及正确的排序见[这篇博客][Link 2] 【代码~】

灰太狼/ 2021年11月26日 07:22/ 0 赞/ 343 阅读

相关 NOIP模拟 8

T1 水题，可是没A，惭愧。值得一提的是，虽然我忘了kmp，现场制造的kmp因为缺少针对题目的特判挂了，但是现场制造的kmp板子能过字符串板子题.. 对..把板子改装了

淩亂°似流年/ 2021年11月09日 06:22/ 0 赞/ 324 阅读

相关 NOIP模拟12

　　也算是最近几次比较水的一次吧。　　考试时看T1像个打表找规律的题，扔了，去看T2，带修莫队？？不会，完戏。看了T3，我决定还是去看T1。　　看着T1，我突然发现T2

冷不防/ 2021年10月26日 14:58/ 0 赞/ 319 阅读