本文主要是介绍蓝桥杯20年第十一届国赛-答疑|贪心,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:
蓝桥杯2020年第十一届国赛真题-答疑 - C语言网 (dotcpp.com)
思路:
这道题 计算的是时刻之和,写出这个时刻之和的计算式子,以下的si,ai的i为任意次序答疑的同学编号 ,不等于输入的顺序
时刻之和=(0+s1+a1) + (s1+a1+e1 +s2+a2)+ (s1+a1+e1 +s2+a2+e2 +s3+a3)+.........+(前面n-1个同学的答疑时间+sn+an)
发现总和即等于 s之和+a之和,加 n-1个前缀和
要使 这个总和最小, s之和+a之和是确定的,那么就要保证 n-1个前缀和最小 ,于是从小到大排序,得到的n-1个前缀和 是最小的 。
代码:
//#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e3+10;int n,ans=0;
/*这道题 计算的是时刻之和,写出这个时刻之和的计算式子,以下的si,ai的i为任意次序答疑的同学编号 ,不等于输入的顺序
时刻之和=(0+s1+a1) + (s1+a1+e1 +s2+a2)+ (s1+a1+e1 +s2+a2+e2 +s3+a3)+.........+(前面n-1个同学的答疑时间+sn+an)
发现总和即等于 s之和+a之和,加 n-1个前缀和
要使 这个总和最小, s之和+a之和是确定的,那么就要保证 n-1个前缀和最小 ,于是从小到大排序,得到的n-1个前缀和 是最小的
*/
int s,a,e;
int su[N];
void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>s>>a>>e;su[i]=s+a+e;ans+=s+a;}//用sort函数的时候greater<int>后还有一对括号 //注意第一个参数是起始位置,这里数组从1开始存的,要改成su+1 sort(su+1,su+n+1,less<int>());for(int i=1;i<n;i++){su[i]=su[i-1]+su[i];ans+=su[i];}cout<<ans;
}signed main() {cout.tie(0);cin.tie(0);solve();return 0;
}
这篇关于蓝桥杯20年第十一届国赛-答疑|贪心的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!