牛客小白月赛2

链接：https://www.nowcoder.com/acm/contest/86/A
来源：牛客网

数字方阵
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

 总是对数字的神秘感感到好奇。这次，他在纸上写下了  个从 到 的数字，并把这些数字排成了 的方阵。他惊奇地发现，这个方阵中每行、每列和两条主对角线上的数字之和都不一样。他想要更多的方阵，但他再写不出来了。于是他㕛跑来找你，请你给他一个边长为  的满足上述性质的方阵。

输入描述:

输入共一行，一个整数 
 ，意义同题面描述。

输出描述:

输出共 
行，每行 
个整数，表示答案方阵。
输出任意一种可行方案即可。
示例1

输入

3

输出

1 2 3
8 9 4
7 6 5

备注:

 
这题比赛的时候没有做出来，但是大神们给出了规律，就是如下代码所示的规律。 
 
 1 #include <iostream>
 2 
 3 using namespace std;
 4 int n;
 5 
 6 int main(){
 7     cin>>n;
 8     int k = 1;
 9     int kk = n*(n-1)+1;
10     for(int i=0;i<n;i++){
11         for(int j=0;j<n;j++){
12             if(j!=n-1)
13                 cout<<k++<<" ";
14             else
15                 cout<<kk++<<" ";
16         }
17         cout<<endl;
18     }
19 
20     return 0;
21 }

链接：https://www.nowcoder.com/acm/contest/86/B
来源：牛客网

小马过河
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

 开始涉猎几何领域了。他现在正在研究小马喝水问题。
众所周知，这个问题中有一匹口渴的小马，一条笔直的河，以及小马的家。小马需要去河边喝水，然后再去家里。它需要走最短的路径。

解决这个问题也很简单，其中有一个步骤是要做小马家关于河水的对称点。
正对此感到一些烦恼。他不会做这个。他想请你帮他作一条过小马家且垂直于河水的线，然后告诉 垂足的位置。

输入描述:

第一行一个整数 
 ，表示 
 的询问个数。
接下去 
 行，每行 
 个实数 
，表示小马家在点 
 ，河水为直线 

输出描述:

输出共 
 行，每行两个实数 
， 表示答案垂足点的坐标 
。 
当你的答案与标准输出的误差小于  时，视为答案正确。
示例1

输入

3
0 1 0 0 1 1
2.13 -6.89 1.78 1.20 -7.73 0.56
3.473 -4.326 -4.851 -0.819 2.467 -2.729

输出

0.5000000 0.5000000
1.5864392 1.1869738
3.7990750 -3.076672

备注:





 


这个就是精度问题，用直线相互垂直，斜率相乘等于-1，然后两直线相交。


求出点的坐标表达式。


 






 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int t;
 7     scanf("%d",&t);
 8     for(int i=0;i<t;i++){
 9         double x1,x2,x3,y1,y2,y3,k1,k2;
10         cin>>x1>>y1>>x2>>y2>>x3>>y3;
11         if(x2==x3)
12             printf("%.7lf %.7lf
",x2,y1);
13         else if(y2==y3)
14             printf("%.7lf %.7lf
",x1,y2);
15         else{
16             k1=(y3-y2)/(x3-x2);
17             k2=(x2-x3)/(y3-y2);
18             double x,y;
19             x=(y2-y1-(k1*x2-k2*x1))/(k2-k1);
20             y=(k2*(y2-y1-k1*x2+k1*x1))/(k2-k1)+y1;
21             printf("%.7lf %.7lf
",x,y);
22         }
23     }
24     return 0;
25 }






链接：https://www.nowcoder.com/acm/contest/86/C
来源：牛客网





真真假假













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

 64bit IO Format: %lld









题目描述









  乾为天，刚健中正，自强不息；坤为地，柔顺伸展，厚载万物。
 乾卦：天行健，君子以自强不息。困龙得水好运交，不由喜气上眉梢，一切谋望皆如意，向后时运渐渐高。
 坤卦：地势坤，君子以厚德载物。肥羊失群入山岗，饿虎逢之把口张，适口充肠心欢喜，卦若占之大吉昌。  


  算卦先生来问你，对于每个他给出的 C++ 头文件，请告诉他是否存在。 


  头文件列表：algorithm, bitset, cctype, cerrno, clocale, cmath, complex, cstdio, cstdlib, cstring, ctime, deque, exception, fstream, functional, limits, list, map, iomanip, ios, iosfwd, iostream, istream, ostream, queue, set, sstream, stack, stdexcept, streambuf, string, utility, vector, cwchar, cwctype 






输入描述:


第一行一个正整数  ，表示询问个数。


接下去  行，每行一个仅由小写字母构成的字符串  ，表示一个询问。 


输出描述:


输出共 



 行，每行一个字符串 



 表示这个头文件存在，或 



 表示这个头文件不存在。 





示例1






输入




3
cstdio
splay
fstream








输出




Qian
Kun
Qian










备注:







每个询问字符串 



 中保证不存在标点、空格或其他不可见字符。




这应该算是签到题，这里就不讲了。




 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 set<string> st;
 5 int main(){
 6     int t;
 7     string s[35]={"algorithm", "bitset", "cctype", "cerrno", "clocale", "cmath", "complex", "cstdio", "cstdlib", "cstring","ctime", "deque", "exception", "fstream", "functional", "limits", "list", "map", "iomanip", "ios", "iosfwd", "iostream", "istream", "ostream", "queue", "set", "sstream", "stack", "stdexcept", "streambuf", "string", "utility", "vector", "cwchar", "cwctype"};
 8     for(int i=0;i<35;i++){
 9         st.insert(s[i]);
10     }
11     cin>>t;
12     while(t--){
13         string ss;
14         cin>>ss;
15         if(st.count(ss)){
16             cout<<"Qian"<<endl;
17         }else{
18             cout<<"Kun"<<endl;
19         }
20 
21     }
22     return 0;
23 }






链接：https://www.nowcoder.com/acm/contest/86/D
来源：牛客网





虚虚实实













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

 64bit IO Format: %lld









题目描述









  震为雷，临危不乱，亨通畅达；巽为风，柔顺伸展，厚载万物。 
 震卦：洊雷，震，君子以恐惧修省。一口金钟在淤泥，人人拿着当玩石，忽然一日钟悬起，响亮一声天下知。
 巽卦：随风，巽，君子以申命行事。一叶孤舟落沙滩，有篙无水进退难，时逢大雨江湖溢，不用费力任往返。  



 算卦先生来问你，对于每个他给出的无向图，是否存在一条路径能够经过所有边恰好一次，并且经过所有点？不需要满足最后回到起点。 


输入描述:


第一行一个数 



 ，表示有 



 组数据。对与每组数据，第一行有两个数 



，接下去 



 行每行两个数 



描述一条无向边 



。图不保证联通。


输出描述:


对于每组数据，如果存在，输出 



 ，否则输出 



 。 





示例1






输入




2
2 2
1 1
2 1
4 6
1 3
1 4
1 2
3 2
4 2
4 3








输出




Zhen
Xun










备注:










 


 


这题就是判断是不是欧拉回路，或欧拉通路。


欧拉回路就是当图中所有点的度数只有两个度数为奇数或全都为偶数，


 


但是要注意一点就是，最后要判断是不是有两个分开的欧拉回路，


我当时就忘了这点，卡了一段时间的bug。


 






 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #define N 50
 5 using namespace std;
 6 vector<int> v[N];
 7 int vis[N];
 8 int sum = 1;
 9 void dfs(int a){
10     vis[a] =1;
11     for(int i=0;i<v[a].size();i++){
12         if(vis[v[a][i]]==0){
13             vis[v[a][i]]=1;
14             dfs(v[a][i]);
15             sum++;
16         }
17     }
18 }
19 int main(){
20     int t;
21     cin>>t;
22     while(t--){
23         int n,m;
24         cin>>n>>m;
25         for(int i=0;i<m;i++){
26             int x,y;
27             cin>>x>>y;
28             if(x==y)
29                 continue;
30             else{
31                 v[x].push_back(y);
32                 v[y].push_back(x);
33             }
34         }
35         memset(vis,0,sizeof(vis));
36         sum = 1;
37         dfs(1);
38         int count = 0;
39         bool prime = true;
40         for(int i=1;i<=n;i++){
41             int a = v[i].size();
42             if(a&1)
43                 count++;
44             if(a==0)
45                 prime = false;
46         }
47         if(prime&&(count==2||count==0)&&sum==n){
48             cout<<"Zhen"<<endl;
49         }else{
50             cout<<"Xun"<<endl;
51         }
52         for(int i=0;i<=n;i++)
53             v[i].clear();
54     }
55 
56 
57     return 0;
58 }






链接：https://www.nowcoder.com/acm/contest/86/E
来源：牛客网





是是非非













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

 64bit IO Format: %lld









题目描述









  坎为水，险阳失道，渊深不测；离为火，依附团结，光明绚丽。
 坎卦：水洊至，习坎；君子以常德行，习教事。一轮明月照水中，只见影儿不见踪，愚夫当财下去取，摸来摸去一场空。
 离卦：明两作，离，大人以继明照四方。官人来占主高升，庄农人家产业增，生意买卖利息厚，匠艺占之大亨通。  


  有一些石子堆，第  堆有  个石子。你和算卦先生轮流从任一堆中任取若干颗石子（每次只能取自一堆，并且不能不取），取到最后一颗石子的人获胜。  


  算卦先生来问你，如果你先手，你是否有必胜策略？若是改动其中几个石子堆中石子的数量呢？ 






输入描述:


第一行两个正整数 ，表示有  个石堆， 次操作。 


第二行  个整数，第  个数  表示第  个石堆初始有  个石子。 


接下去  行，每行两个正整数  ，表示把第  堆石子的个数修改成 。操作是累计的，也就是说，每次操作是在上一次操作结束后的状态上操作的。


输出描述:


共  行，输出每次操作之后先手是否有必胜策略。


如果有，输出  ，否则输出  。 







示例1






输入




5 4
6 7 3 4 5
1 6
2 1
2 4
5 5








输出




Kan
Kan
Li
Li










备注:










 


此时后就要用到博弈了，


这就是一个典型的尼姆博弈


利用异或运算，如果所有堆中的数异或的结果不为0，则先取者获胜。


 






 1 #include <iostream>
 2 #define N 1000000
 3 using namespace std;
 4 
 5 int a[N];
 6 int main(){
 7     int n,m;
 8     cin>>n>>m;
 9     int sum = 0;
10     for(int i=1;i<=n;i++){
11         cin>>a[i];
12         sum=sum^a[i];
13     }
14     while(m--){
15         int x,y;
16         cin>>x>>y;
17         sum=sum^a[x];
18         a[x] = y;
19         sum=sum^a[x];
20         if(sum==0){
21             cout<<"Li"<<endl;
22         }else{
23             cout<<"Kan"<<endl;
24         }
25     }
26     return 0;
27 }






链接：https://www.nowcoder.com/acm/contest/86/F
来源：牛客网





黑黑白白













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

 64bit IO Format: %lld









题目描述









  艮为山，动静得宜，适可而止；兑为泽，刚内柔外，上下相和。
 艮卦：兼山，艮；君子以思不出其位。财帛常打心头走，可惜眼前难到手，不如意时且忍耐，逢着闲事休开口。
 兑卦：丽泽，兑；君子以朋友讲习。这个卦象真可取，觉着做事不费力，休要错过这机关，事事觉得随心意。 


  有一个棋子放在一颗有根树的根上。你和算卦先生轮流把这个棋子向所在点的其中一个儿子移动（只能移动到儿子）。不能再移动就算失败（即棋子所在节点没有儿子）。 


  算卦先生来问你，如果你先手，你是否有必胜策略？  






输入描述:


第一行一个数 ，表示有  组数据。


接下去每组数据的第一行有两个数  ，表示树有  个节点，其中  为根节点编号（从  开始编号）。 


接下去  行每行两个数字  ，表示点  和  之间有一条边。 


输出描述:


每组数据输出一行，



 表示先手有必胜策略，



表示没有。 





示例1






输入




2
3 1
1 2
2 3
5 4
1 2
1 3
3 4
4 5








输出




Dui
Gen










备注:










 


 


该题就是找到一条合适的路就行。


首先脱离代码来分析一下思路。


要是有必胜策略，那么就要在有一条必胜的路，


比如直接有一条没有分支的奇数点的一条路就是一条必胜路。


再这如果有分支的话，那我们又要怎样做呢，当然是做最坏的打算了。


每到一个分支点我们要判断这个是从根节点下来的奇数点还是偶数点，


但是返回到代码的话，要是暴力的话就会超时，所以可以用dfs的方法


间隔性的返回真或假。


仔细研究代码就知道啦。


 






 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #define N 10005
 5 using namespace std;
 6 vector<int> v[N];
 7 int t;
 8 int vis[N];
 9 bool dfs(int index){
10     vis[index] = 1;
11     for(int i=0;i<v[index].size();i++){
12         int a = v[index][i];
13         if(!vis[a]){
14             bool prime = dfs(a);
15             if(!prime)
16                 return true;
17         }
18     }
19     return false;
20 }
21 int main(){
22     cin>>t;
23     while(t--){
24         memset(vis,0,sizeof(vis));
25         int n,m;
26         cin>>n>>m;
27         for(int i=0;i<N;i++)
28             v[i].clear();
29         for(int i=0;i<n-1;i++){
30             int x,y;
31             cin>>x>>y;
32             v[x].push_back(y);
33             v[y].push_back(x);
34         }
35         bool prime = dfs(m);
36         if(prime)
37             cout<<"Gen"<<endl;
38         else
39             cout<<"Dui"<<endl;
40         
41     }
42     return 0;
43 }






链接：https://www.nowcoder.com/acm/contest/86/G
来源：牛客网





文













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

 64bit IO Format: %lld









题目描述









  Sεlιнα(Selina) 开始了新一轮的男友海选。她要求她的男友要德智体美劳样样都全。首先进行的是文化知识竞赛。 


  Sεlιнα 精心准备了一套选择题，每个选择题有且只有一个正确答案。她邀请参赛男友们来答题，并回收了试卷准备批改。可是她却犯了愁。她不知道怎么快速地批改完这些试卷。她知道你是计算机大佬，就跑来请你写个程序帮她批改试卷。 


  Sεlιнα 会给你一份标准答案，再给你每个参赛男友的答卷。答卷中的每道题可能有一个答案， 也可能没有作答。你要做的是最后告诉 Sεlιнα 谁拿到了最高分，以及最高分的分数（分数为  分制）。Sεlιнα 喜欢优美的名字，所以如果有同样的分数，请告诉她其中字典序最小的选手名字。 


  不要偷懒哦！要是你告诉了 Sεlιнα 错误的答案，她会很生气的！ 






输入描述:


第一行两个整数 ，表示有  道选择题和  个参赛男友。第二行一个长为  的字符串，表示标准答案。其中第  个字母表示第  个选择题的答案。保证所有字母在  中。接下去  行，每两行表示一个参赛男友： 


 · 第一行一个字符串，表示参赛者姓名，保证姓名仅由大小写字母组成；


 · 第二行一个长为  的字符串，表示该参赛者的答案。其中第  个字母表示该参赛者对于第  个选择题的答案。保证所有字母在  中。 表示该参赛者未作答此题。


输出描述:


输出共两行，第一行是最高分的参赛男友姓名，第二行为其分数。


分数为  分制，保留两位小数。若有多人同分，输出字典序最小的姓名。 







示例1






输入




5 3
ADBBC
spiderman
ADBAC
niconico
BDXBC
ekstieks
ACBBC








输出




ekstieks
80.00










备注:







 姓名长度  


 


这题就是sort+cmp，然后注意一下输出。






 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 struct Node{
 6     string na;
 7     double sor;
 8 };
 9 bool cmp(Node x,Node y){
10     if(x.sor==y.sor)
11         return x.na<y.na;
12     return x.sor>y.sor;
13 }
14 Node ans[100005];
15 int main(){
16     int n,m;
17     cin>>n>>m;
18     string s;
19     cin>>s;
20     int len = s.length();
21     for(int i=0;i<m;i++){
22         double cnt = 0;
23         string name,an;
24         cin>>name>>an;
25         for(int i=0;i<len;i++)
26              if(an[i]==s[i])
27                  cnt++;
28         ans[i].na = name;
29         ans[i].sor = (100.0/(double)len)*cnt;
30     }
31     sort(ans,ans+m,cmp);
32     cout<<ans[0].na<<endl;
33     printf("%.2f
",ans[0].sor);
34     return 0;
35 }






链接：https://www.nowcoder.com/acm/contest/86/H
来源：牛客网





武













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

 64bit IO Format: %lld









题目描述









  其次，Sεlιнα(Selina) 要进行体力比武竞赛。 


  在 Sεlιнα 所在的城市，有  个街区，编号为 ，总共有  条的街道连接这些街区， 使得每两个街区之间都直接或间接地有街道将它们相连。Sεlιнα 把通过了文化知识竞赛的参赛男友们召集到她家所在的街区  ，并以这个街区为起点，让所有参赛男友们向其他街区跑去。这些参赛者们被命令不准重复跑某条街道，而且在规定时间内要尽可能地跑远。比赛结束后，所有参赛者将停留在他们此时所在的街区。之后 Sεlιнα 开始视察结果。现在她知道每个街区都有一些她的参赛男友停留着，她现在想先去看看离她家第  近的街区。所以作为一位好帮手，你的任务是要告诉她所有街区中，离 Sεlιнα 家第  近的街区与 Sεlιнα 家之间的距离。  






输入描述:


第一行三个整数，，含义同题面描述。


接下去  行，每行三个整数，，表示从第  个街区到第  个街区有一条权值为 的街道相连。街区从  开始标号。


输出描述:


输出共一行，一个整数，表示所有街区与 Sεlιнα 家所在街区之间最近距离的第 



 小值。 





示例1






输入




3 3 2
1 2 4
2 3 5








输出




9












示例2






输入




6 4 3
1 2 7
2 3 2
2 4 2
2 5 10
3 6 3








输出




7










备注:







 


这题就是bfs走一遍，把路径的长度存在数组里，最后输出就行。


 






 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 #include <queue>
 5 #define N 100005
 6 #define ll long long int
 7 using namespace std;
 8 struct Node{
 9     int to;
10     int val;
11 };
12 vector<Node> ve[N];
13 ll ans[N];
14 int vis[N];
15 void bfs(int x){
16     vis[x] = 1;
17     queue<int> q;
18     ans[x] = 0;
19     q.push(x);
20     while(!q.empty()){
21         int aa=q.front();
22         q.pop();
23         for(int i=0;i<ve[aa].size();i++){
24             Node a = ve[aa][i];
25             if(vis[a.to]==0){
26                 ans[a.to] = ans[aa]+a.val;
27                 // cout<<ans[a.to]<<endl;
28                 q.push(a.to);
29                 vis[a.to] = 1;
30             }
31         }
32     }
33 }
34 int main(){
35     int n,m,k;
36     cin>>n>>m>>k;
37     for(int i=0;i<n-1;i++){
38         int u,v,w;
39         cin>>u>>v>>w;
40         Node t;
41         t.to = v,t.val = w;
42         ve[u].push_back(t);
43         t.to = u;
44         ve[v].push_back(t);
45     }
46     bfs(m);
47     sort(ans,ans+n+1);
48     cout<<ans[k+1]<<endl;
49     return 0;
50 }





链接：https://www.nowcoder.com/acm/contest/86/I
来源：牛客网





艺













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

 64bit IO Format: %lld









题目描述









  接下去，Sεlιнα(Selina) 又搞了个文艺竞演。 


  虽说是文艺竞演，其实只是为了满足 Sεlιнα 的内心企盼——看群男友献歌献舞。她排列好了各个参赛男友的节目顺序，然后将他们安排在两个舞台上表演，自己则在演播室里使用两台闭路电视同时观看。万万没想到的是，当一切准备就绪时，其中一台电视炸了，她不会修，也没有时间修。于是只能尴尬地使用一台闭路电视观看两个舞台上的节目。当然，这台电视不支持分屏同时观看，所以 Sεlιнα 只能不停地换台观看。现在，作为导演的 Sεlιнα 已经知道了两个舞台的节目 单以及每个节目  对于她所能产生的愉悦度  ，她想安排电视在每个时刻播放的频道（可以在某些时刻不看），使得自己能得到最大的愉悦度。现在请优秀的你告诉 Sεlιнα 最大能产生的愉悦度是多少。  


  要注意的是，文艺竞演没有广告插播，所以当一个节目结束时，另一个节目会立刻开始演出。 并且 Sεlιнα 看节目以分钟为单位，也就是说，她只能在每分钟结束的那一刻切换舞台。节目对 Sεlιнα 产生愉悦度是以分钟为单位的，也就是说，她看第  个节目每一分钟就会产生  的愉悦度。而 Sεlιнα 对节目的完整性丝毫不在意，没有完整地看一个节目是没有关系的。   






输入描述:


第一行三个数 ，表示舞台一有  个节目，舞台二有  个节目，总时长为  分钟。


接下去  行，每行两个整数  ，表示舞台一的第  个节目在第  分钟结束后开始，每分钟能产生愉悦度  。当一个节目开始时，这个舞台之前正在播放的节目直接停止，中间没有暂停。


接下去  行，每行两个整数  ，表示舞台二的第  个节目在第  分钟结束后开始，每分钟能产生愉悦度  。当一个节目开始时，这个舞台之前正在播放的节目直接停止，中间没有暂停。


数据保证每个舞台都有一个在  分钟时开始的节目（即最开始的节目），并且在同一个舞台中没有两个节目开始时间相同（即没有一个节目时长为 ）。数据不保证输入中每个舞台的  会从小到大排序。 


输出描述:


输出共一行，一个整数，表示最大的愉悦度。





示例1






输入




2 2 5
2 3
0 2
0 3
3 1








输出




15








说明




在这个样例中，Sεlιнα 在开始时观看频道二的节目，每分钟产生愉悦度 



 ；在第二分钟结束时刻切换到频道一，每分钟产生愉悦度 

 ，然后直到结束。总共产生愉悦度  。 










示例2






输入




3 4 17
8 3
0 10
9 10
7 15
0 6
16 9
14 8








输出




205










备注:













这题就是要找到，哪一分钟获得的喜悦值更高并且大于0，


所以就可以用sort先排序开始的时间，然后用类似于指针的方式来


走遍所有的时间点。





 1 #include <iostream>
 2 #include <algorithm>
 3 #define mem(a) memset(a,0,sizeof(a))
 4 #define N 100015
 5 #define ll long long int
 6 using namespace std;
 7 
 8 struct Node{
 9     ll st, val;
10 };
11 bool cmp(Node x,Node y){
12     return x.st<y.st;
13 }
14 Node a[N],b[N];
15 int n,m,t;
16 int main(){
17     ios::sync_with_stdio(false);
18     cin>>n>>m>>t;
19     for(int i=0;i<n;i++){
20         cin>>a[i].st>>a[i].val;
21     }
22     for(int i=0;i<m;i++){
23         cin>>b[i].st>>b[i].val;
24     }
25     a[n].st=t;
26     b[m].st=t;
27     sort(a,a+n,cmp);
28     sort(b,b+m,cmp);
29     ll al = 0,bl = 0,now = 0,ans = 0;
30     while(now<t){
31         int cnt;
32         if(a[al].val>b[bl].val){
33             cnt = a[al].val;
34         }else{
35             cnt = b[bl].val;
36         }
37         int pre = now;
38         now = min(a[al+1].st,b[bl+1].st);
39         if(cnt>0)
40             ans+=cnt*(now-pre);
41         if(now==t) break;
42         if(now == a[al+1].st) al++;
43         if(now == b[bl+1].st) bl++;
44     }
45     cout<<ans<<endl;
46     return 0;
47 }






链接：https://www.nowcoder.com/acm/contest/86/J
来源：牛客网





美













时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

 64bit IO Format: %lld









题目描述









  最后，Sεlιнα(Selina) 开始了选美大赛。 一如既往地，Sεlιнα 想最大化自己的愉悦度。她品味十分独特，对“美”有自己独到的见解。 她给每位经过层层选拔来到这一关的参赛男友都定义了一个帅气值  。Sεlιнα 需要将这些参赛者排成一排，她对于这个排列的“美”值的定义是：  


  
 


  其中  表示排列中第  个人的帅气值。特别地，当  时，有  。 


  她依旧想使自己获得最大的愉悦值，所以她要使这个排列的  值尽可能地大。聪明的你，快来告诉 Sεlιнα，这个最大的值是多少。 
 






输入描述:


第一行一个整数  ，表示有  个男友。


第二行  个整数，第  个数表示值  。 


输出描述:


输出共一行，一个整数，表示最大的 



 值。 





示例1






输入




5
7 3 15 12 8








输出




34












示例2






输入




7
-2 0 8 9 -5 3 10








输出




68










备注:







 


这题看完之后，脑袋里就一个想法，最大的接一个最小的，然后第二大的，第二小的，依次循环，


所以我就用了两个数组一个从大到小，一个从小到大。


然后相互减，然后相加除二，但是其中有几个注意的点，在代码里有体现出来。


最后要加上最大的减去循环最后的那一个数。


 






 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #define N 100005
 5 #define ll long long int
 6 using namespace std;
 7 int a[N],b[N];
 8 int main(){
 9     int n;
10     cin>>n;
11     for(int i=0;i<n;i++){
12         cin>>a[i];
13     }
14     sort(a,a+n);
15     for(int i=0;i<n;i++){
16         b[i] = a[n-i-1];
17     }
18     ll sum = 0;
19     for(int i=0;i<n;i++){
20         sum+=abs(a[i]-b[i]);
21     }
22     for(int i=0;i<n-1;i++){
23         sum+=abs(a[i]-b[i+1]);
24     }
25     int k;
26     sum=sum/2;
27     if(n%2==0) k = n/2;
28     else k = n/2+1;
29         
30     sum+=abs(a[k-1]-b[0]);
31     cout<<sum<<endl;
32     return 0;
33 }






















































        

	      

	    

	  

	  

	    
      
        【推广】
        免费学中医，健康全家人
      
	  

    

    

          原文地址：https://www.cnblogs.com/zllwxm123/p/8921770.html