上海计算机学会2024年8月月赛C++丙组T5划分（二）
发布时间
阅读量：
阅读量
划分（二）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个长度为 n 的排列 p1,p2,...,pn，请你将其划分成 m 个连续段，并最大化每个连续段中最大值的和，并求出取到该最大值有多少种方案？（方案数对10^9+7取模）
输入格式
输入共两行：
第一行，两个正整数 n,m 表示排列的长度和划分的段数。
第二行，n 个正整数，表示给定的排列。
输出格式
输出共两行：
第一行，一个正整数表示划分后能取到的最大和。
第二行，一个正整数，表示方案数对10^9+7取模。
数据范围
- 对于 30% 的数据，1≤m≤n≤20
- 对于 60% 的数据，1≤m≤n≤10^3
- 对于 100% 的数据，1≤m≤n≤10^5
样例数据
输入:
4 2
4 1 3 2
输出:
7
2
说明:
两种划分方法能取到7
方案1： 4 | 1 3 2 --> 第一段最大值是4、第二段最大值是3，总和为7
方案2： 4 1 | 3 2 --> 第一段最大值是4、第二段最大值是3，总和为7
输入:
4 4
3 2 1 4
输出:
10
1
解析：
先按大小排序，找出前m大的数，然后确定他们的位置，然后找出每两个数之间可以加入几个隔板，使用乘法原理算出结果，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n, m;
struct node {
int x;//数字
int no;//位置
};
node a[100005];
bool cmp(node x, node y) {//按数字从大到小排列
return x.x > y.x;
}
bool cmp1(node x, node y) {//按位置从小到大排列
return x.no < y.no;
}
long long ans = 1;//方案数
long long sum = 0;//和
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i].x;
a[i].no = i;
}
sort(a + 1, a + n + 1, cmp);//全部按数字从大到小排列
sort(a + 1, a + m + 1, cmp1);//前m大的，按位置从小到大排列
for(int i = 1; i < m; i++) {
ans *= (a[i + 1].no - a[i].no);//乘法原理计算方案数
ans %= 1000000007;
sum += a[i].x;//求和
}
cout << sum + a[m].x << endl << ans;
return 0;
}
O(N)的解法：
已知最大的m个数为n-m+1...n，那么直接可以遍历一遍，找到他们的位置，算出答案。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[100005];
long long ans = 1;
int main() {
cin >> n >> m;
int d = n - m + 1;//计算前m大的数中最小的那个
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int t = 0; //上一个前m大的数出现的位置
for(int i = 1; i <= n; i++) {
if (a[i] >= d) { //如果是前m大的数
if (t > 0) { //不是第一个
ans *= i - t; //乘法原理
ans %= 1000000007;
}
t = i; //记录出现的位置
}
}
//等差数列求和
cout << (long long)(d + n)*m / 2 << endl << ans;
return 0;
}
全部评论 (0)
还没有任何评论哟~