“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛----E-CSL的魔法

本文主要是介绍“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛----E-CSL的魔法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

首先发出题目链接:
链接:https://ac.nowcoder.com/acm/contest/551/E
来源:牛客网

题目如下:
题目内容
描述
很明显,如果要满足a0b0+a1b1+·····+anbnn最小

我们就要按如下方式进行对应:

a0为a序列的最大(小)值 且 b0为b序列的最小(大)值
a1为a序列的第二大(小)值 且 b1为b序列的第二小(大)值
a2为a序列的第三大(小)值 且 b2为b序列的第三小(大)值
·
·

an为a序列的最小(大)值 且 bn为b序列的最大(小)值

我们可以以一个序列为基准,只交换另一个序列里的元素,使被交换元素的这个序列里的元素按照如上对应方式与基准序列进行严格的对应(举个例子,比如a序列为{5,2,4,3,1},b序列为{4,1,3,5,2},我们可以让a序列不动,将b序列进行元素交换,使b序列变成{1,4,2,3,5}即可,交换b序列元素的次数即为答案

而问题在于,如何得到这个次数cnt的值


思路:

可以将初始序列每个元素加一个独一无二的标记(标记最好是升序数值,或者降序数值),为了方便,我们给每个元素的标记数设为此元素在当前序列中的位置(比如刚刚那个a序列我们加上标记之后就变成了{{5,1},{2,2},{4,3},{3,4},{1,5}},使序列成为一个个数对,数对的第一个值是数值大小,第二个值是这个数在a序列的位置(数值标记),同理,b序列变成了{{4,1},{1,2},{3,3},{5,4},{2,5}})

那么标记之后有什么用捏?

我们将两个序列关于数值大小排序,使得两个序列中一个序列数值大小为升序排列,一个数值大小为降序排列(选哪个序列是任意的),当排完之后,数对的数值大小就是有序的了,而数值标记则成为了乱序

排序后,a序列(升序)为{{1,5},{2,2},{3,4},{4,3},{5,1}},b序列(降序)为{{5,4},{4,1},{3,3},{2,5},{1,2}};

由于我们只在意两个序列对应位置元素乘积的和的最值,故不用考虑序列本身元素是否有序(集合的无序性),因此基准序列(我们假设a序列是基准序列)在排序前和排序后在此题是等效的,而另一个序列(排序后的b序列)则成为了原来序列(排序前的b序列)经过cnt次交换数值得到的与基准序列(a序列)进行严格对应的序列。

要求cnt的最小值,我们可以进行模拟,将排序后的b序列通过贪心交换法,变成排序前的b序列,每次交换,cnt就加一,那这个cnt就是最后的答案。

如何贪心交换?这时序列的标记就起了作用,我们只要让b序列和基准序列(a序列)的数值标记对应相等就行了
a序列不变:
{{1,5},{2,2},{3,4},{4,3},{5,1}}
让b序列:
{{5,4},{4,1},{3,3},{2,5},{1,2}}
进过交换数对,成为新的b序列:
{{2,5},{1,2},{5,4},{3,3},{4,1}}
两个序列数据标记对应相等,就像未排序前的两个序列数据标记对应相等一样

因此,我们现在只用考虑数值标记而可以忽略数值大小。

为了使对应数组标记相等,我们重新定义一个数组diff,数组diff存b序列元素的数值标记,数组diff下标为b序列排序后的数值标记(即diff[a序列数值下标]=b序列对应数值下标,对于这个例子diff[5]=4,diff[2]=1,diff[4]=3,diff[3]=5,diff[1]=2

将这个这个数组变成diff[i]=i的最小步骤数cnt即为答案,很简单的模拟排序问题。


cnt初始化等于0,遍历diff数组,如果发现diff[i]!=i,就重新定义一个t,将diff[i]的值赋给t,然后令diff[i]=0(相当于我们把diff[i]的值拿出来,用0来表示diff[i]为空),然后开始循环断diff[t]是否等于t,如果diff[t]不等于t,就交换diff[t]和t的值,并将cnt++(相当于把原来diff[t]的值取出来,然后令diff[t]=t,千万不要写成下面样子)

t=diff[t];//这样写就把t的值首先给改变了
diff[t]=t;

可以按下面这样写

int x=diff[t];
diff[t]=t;
t=x;//这样写就先把diff[t]的值取出来放到一边,令diff[t]=t,在把放到一边的值存到t里面。

也可以用swap语句

swap(diff[t],t);

这样循环判断,直到当diff[t]=0的时候(这样搬动数据是一个循环,一定会出现diff[t]=0),就直接令diff[t]=t;

然后往下继续遍历数组diff


过程:

idiff[i]
12
21
35
43
54
t

diff[1]!=1 (diff[1]=2),于是将diff[1]的值剪切给t

idiff[i]
10
21
35
43
54
t2

diff[t]!=t(diff[t]=1),swap[diff[t],t](交换值),cnt++

idiff[i]
10
22
35
43
54
t1

diff[t]=0,将t的值剪切给diff[t]

idiff[i]
11
22
35
43
54
t

diff[3]!=3(diff[3]=5),于是将diff[3]的值剪切给t

idiff[i]
11
22
30
43
54
t5

diff[t]!=t(diff[t]=4),swap[diff[t],t](交换值),cnt++

idiff[i]
11
22
30
43
55
t4

diff[t]!=t(diff[t]=3),swap[diff[t],t](交换值),cnt++

idiff[i]
11
22
30
44
55
t3

diff[t]=0,将t的值剪切给diff[t]

idiff[i]
11
22
33
44
55
t

结束,cnt=3


代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;//使用STL库里的数对存数值大小和数值标记,其中first为数值大小,second为数值标记
P magic1[100005],magic2[100005];//两个数对类型的序列
int sign[100005]={0}; //之前说的只用了存两个序列数值标记的数组,其中数组下表是a序列的数值标记,数组存的值为b序列数组标记
int cnt=0;//输出的结果
int t,n;
bool comp1(P a,P b){return a.first>b.first;
}
bool comp2(P a,P b){return a.first<b.first;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>t;magic1[i].first=t;magic1[i].second=i;}for(int i=1;i<=n;i++){cin>>t;magic2[i].first=t;magic2[i].second=i;}//对两个数组进行赋值sort(magic1+1,magic1+n+1,comp1);sort(magic2+1,magic2+n+1,comp2);//对两个数组关于数值大小排序for(int i=1;i<=n;i++)sign[magic1[i].second]=magic2[i].second;//将两个序列的数值标记拿出来for(int i=1;i<=n;i++){//开始贪心排序,遍历sign数组if(sign[i]!=i){t=sign[i];sign[i]=0;//将sign[i]的值拿出来,那么sign[i]没有值,为空(用0来表示)while(sign[t]!=t && sign[t]!=0){//while(sign[t]存的值不是t && sign[t]不是空的)swap(sign[t],t);//将sign[t]存的值拿出来,把sign[t]应该存的值丢进去cnt++;//次数加一}sign[t]=t;//循环直到sign[i]为空时停止(表面sign[t]为开始拿出来的值的位置,此时t应该等于i)}	}cout<<cnt;return 0;
}

这篇关于“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛----E-CSL的魔法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/586587

相关文章

Andrej Karpathy最新采访:认知核心模型10亿参数就够了,AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人,AI大神Andrej Karpathy,曾是OpenAI联合创始人之一,特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ,宣布将长期致力于AI原生教育。 近日,Andrej Karpathy接受了No Priors(投资博客)的采访,与硅谷知名投资人 Sara Guo 和 Elad G

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

认知杂谈52

今天分享 有人说的一段争议性的话 I I 1拓展人脉很重要** 咱们活在这世上啊,得明白一件事儿,知识、逻辑能力和实战经验虽然重要,但确实都不是最关键的。真正关键的是要懂得怎么和那些手里有资源的人打交道。人脉那可真是一笔无形的大财富呢。你想想看,有时候一个有影响力的人帮你一把,那效果可比你累死累活干一年都强得多。 I I 就比如说,你要是认识个行业里的大牛,他可能给你介绍个特别好的工

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型: 二、常量和变量 2.1常量和符号常量 在程序运行过程中,其值不能被改变的量称为常量。 常量区分为不同的类型: 程序中用#define(预处理器指令)命令行定义变量将代表常量,用一个标识符代表一个常量,称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元,用来存放数据,在程序运行期间,这些值是可以 改变的。 变

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①<(小于) ②<=(小于或等于) ③>(大于) ④>=(大于或等于 ) ⑤==(等于) ⑥!=(不等于) 说明: 前4个优先级相同,后2个优先级相同,关系运算符的优先级低于算术运算符,关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式(可以是算术表达式或关系表达式,逻辑表达式,赋值表达式,字符

基于SSM+Vue+MySQL的可视化高校公寓管理系统

系统展示 管理员界面 宿管界面 学生界面 系统背景   当前社会各行业领域竞争压力非常大,随着当前时代的信息化,科学化发展,让社会各行业领域都争相使用新的信息技术,对行业内的各种相关数据进行科学化,规范化管理。这样的大环境让那些止步不前,不接受信息改革带来的信息技术的企业随时面临被淘汰,被取代的风险。所以当今,各个行业领域,不管是传统的教育行业

2024年AMC10美国数学竞赛倒计时两个月:吃透1250道真题和知识点(持续)

根据通知,2024年AMC10美国数学竞赛的报名还有两周,正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间,认真备考,最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢?做真题,吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一。通过做真题,可以帮助孩子找到真实竞赛的感觉,而且更加贴近比赛的内容,可以通过真题查漏补缺,更有针对性的补齐知识的短板。

智能工厂程序设计 之1 智能工厂都本俱的方面(Facet,Aspect和Respect)即智能依赖的基底Substrate 之1

Q1、昨天分别给出了三个智能工厂的 “面face”(里面inter-face,外面outer-face和表面surface) 以及每个“面face” 各自使用的“方”(StringProcessor,CaseFilter和ModeAdapter)  。今天我们将继续说说三个智能工厂的“方面” 。在展开之前先看一下三个单词:面向facing,取向oriented,朝向toword。理解这三个词 和

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 (请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”) 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及, 以及人们活动范围的不断扩大,城市道 路交通拥堵问题日渐严重,即使在一些非中心城市,道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”,是相关部门的棘手难题之一。 考虑一个拥有知名景区

2024 年高教社杯全国大学生数学建模竞赛 C 题 农作物的种植策略 参考论文 无水印

持续更新中,2024年数学建模比赛思路代码论文都会发布到专栏内,只需订阅一次!  完整论文+代码+数据结果链接在文末!  订阅后可查看参考论文文件 第一问 1.1 问题重述 这个问题围绕的是华北山区的某乡村,在有限的耕地条件下,如何制定最优的农作物种植策略。乡村有 34 块露天耕地和 20 个大棚,种植条件包括粮食作物、蔬菜、水稻和食用菌。除了要考虑地块的面积、种植季节等,还要确保