算法刷题day14

引言

今天做了三道新题,类型是贪心、枚举、DP,不是特别难,但是努力一下刚好能够够得上,还是不错的,只要能够一直坚持下去,不断刷题不断总结,就是记忆力和毅力了,加油!


一、平均

标签:贪心

思路:贪心这种题目只能是见过类似的,然后去变种,一般比赛中是不太可能去现推出来的,这里只讲一下解题思路。这个变数只有四种情况,多变多、多变少、少变多、少变少。
1.多变多:多的给多的,那么一个变少了一个变多了,变多了的肯定又要变成少的,所以相当于第一步就多余了,反而代价多了
2.少变多:少的变多的,那么肯定会有一个多的变成少的,那么就要多变,相当于第一步也就多余了
3.少变少:其中的一个少的变少了,肯定会有一个多的变成这个少的,所以第一步也多余了
所以说只能是多的变少的,由于n的数量刚好,所以多余的部分肯定是会变的,要求又得是代价最少,那么就把多余的代价少的那部分变了就行了。

题目描述:

有一个长度为 n 的数组(n 是 10 的倍数),每个数 ai都是区间 [0,9] 中的整数。

小明发现数组里每种数出现的次数不太平均,而更改第 i 个数的代价为 bi,他想更改若干个数的值使得这 10 种数出现的次数相等
(都等于 n10),请问代价和最少为多少。

输入格式
输入的第一行包含一个正整数 n。

接下来 n 行,第 i 行包含两个整数 ai,bi,用一个空格分隔。

输出格式
输出一行包含一个正整数表示答案。

数据范围
对于 20% 的评测用例,n≤1000;
对于所有评测用例,n≤105,0<bi≤2×105。

输入样例:
10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10
输出样例:
27
样例解释
只更改第 1,2,4,5,7,8 个数,需要花费代价 1+2+4+5+7+8=27。

示例代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int n;
vector<int> arr[10];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        arr[a].push_back(b);
    }
    
    LL res = 0, ave = n / 10;
    for(int i = 0; i < 10; ++i)
    {
        if(arr[i].size() > ave)
        {
            sort(arr[i].begin(), arr[i].end());
            for(int j = 0; j < arr[i].size() - ave; ++j) res += arr[i][j];
        }
    }
    
    cout << res << endl;
    
    return 0;
}

二、三国游戏

标签:枚举

思路:这道题只有三种情况胜出,然后在这其中,

x

i

>

y

i

+

z

i

,

i

(

1

,

n

)

当中任选多个

x_i>y_i+z_i,iin(1,n)当中任选多个

xi>yi+zi,i(1,n)当中任选多个,即

x

i

y

i

z

i

>

0

,

i

(

1

,

n

)

当中任选多个

x_i-y_i-z_i>0,iin(1,n)当中任选多个

xiyizi>0,i(1,n)当中任选多个,可以规定一个

w

i

w_i

wi来表示左半边,也就是有多个

w

i

w_i

wi问最多能选多少个使得它们的和大于0,我们可以把这些

w

i

w_i

wi由大到小排序,然后到了边界条件判断一下就可以了。最后结果从三个国家胜出的最大结果中选最大的就行了。

题目描述:

小蓝正在玩一款游戏。

游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z(一开始可以认为都为 0)。

游戏有 n 个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i 个事件发生时会分别让 X,Y,Z 
增加 Ai,Bi,Ci。

当游戏结束时 (所有事件的发生与否已经确定),如果 X,Y,Z 的其中一个大于另外两个之和,我们认为其获胜。

例如,当 X>Y+Z 时,我们认为魏国获胜。

小蓝想知道游戏结束时如果有其中一个国家获胜,最多发生了多少个事件?

如果不存在任何能让某国获胜的情况,请输出 −1。

输入格式
输入的第一行包含一个整数 n。

第二行包含 n 个整数表示 Ai,相邻整数之间使用一个空格分隔。

第三行包含 n 个整数表示 Bi,相邻整数之间使用一个空格分隔。

第四行包含 n 个整数表示 Ci,相邻整数之间使用一个空格分隔。

输出格式
输出一行包含一个整数表示答案。

数据范围
对于 40% 的评测用例,n≤500;对于 70% 的评测用例,n≤5000;
对于所有评测用例,1≤n≤1050≤Ai,Bi,Ci≤109。
注意,蓝桥杯官方给出的关于 Ai,Bi,Ci 的数据范围是 1≤Ai,Bi,Ci≤109,但是这与给出的输入样例相矛盾,因此予以纠正。

输入样例:
3
1 2 2
2 3 2
1 0 7
输出样例:
2
样例解释
发生两个事件时,有两种不同的情况会出现获胜方。
发生 1,2 事件时蜀国获胜。
发生 1,3 事件时吴国获胜。

示例代码:

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int n;
int a[N], b[N], c[N], w[N];

LL work(int x[], int y[], int z[])  //x国家胜出
{
    for(int i = 0; i < n; ++i) w[i] = x[i] - y[i] - z[i];
    
    sort(w, w+n, greater<int>());
    
    LL sum = 0, res = -1;
    for(int i = 0; i < n; ++i)
    {
        sum += w[i];
        if(sum > 0) res = i + 1;
        else break;
    }
    
    return res;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i) cin >> b[i];
    for(int i = 0; i < n; ++i) cin >> c[i];
    
    LL res = max({work(a, b, c), work(b, a, c), work(c, a, b)});
    cout << res << endl;
    
    return 0;
}

三、松散子序列

标签:状态机DP

思路:这个题目的意思就是从一个字符串中选一段子序列,然后不能选相邻的,然后使得这个子序列的价值最大。这个跟那个小偷偷盗差不多,不能选相邻一家的。然后就是每个字符串有两个状态,选或者不选,

f

[

i

]

[

2

]

f[i][2]

f[i][2]中分别表示前

i

i

i个字母中不选、选第

i

i

i个字母的最大价值,可以推导出方程来

f

[

i

]

[

0

]

=

m

a

x

(

f

[

i

1

]

[

0

]

,

f

[

i

1

]

[

1

]

)

,

f[i][0]=max(f[i-1][0],f[i-1][1]),

f[i][0]=max(f[i1][0],f[i1][1]),

f

[

i

]

[

1

]

=

f

[

i

1

]

[

0

]

+

s

t

r

[

i

]

 

a

 

+

1

f[i][1]=f[i-1][0]+str[i]- 'a' +1

f[i][1]=f[i1][0]+str[i] a +1最后的结果就是从

f

[

n

]

[

0

]

f[n][0]

f[n][0]

f

[

n

]

[

1

]

f[n][1]

f[n][1]中选一个最大的出来就行了。

题目描述:

给定一个仅含小写字母的字符串 s,假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 pi个字符。

我们定义 s 的一个松散子序列为:对于 i>1 总是有 pi−pi−1≥2。

设一个子序列的价值为其包含的每个字符的价值之和(a∼z 分别为 1∼26)。

求 s 的松散子序列中的最大价值。

输入格式
输入一行包含一个字符串 s。

输出格式
输出一行包含一个整数表示答案。

数据范围
对于 20% 的评测用例,|s|≤10;
对于 40% 的评测用例,|s|≤300;
对于  70%  的评测用例,|s|≤5000;
对于所有评测用例,1≤|s|≤106,字符串中仅包含小写字母。

输入样例:
azaazaz
输出样例:
78

示例代码:

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e6+10;

int n;
char str[N];
int f[N][2];

int main()
{
    scanf("%s", str+1);
    n = strlen(str+1);
    
    for(int i = 1; i <= n; ++i)
    {
        f[i][0] = max(f[i-1][0], f[i-1][1]);
        f[i][1] = f[i-1][0] + str[i] - 'a' + 1;
    }
    
    cout << max(f[n][0], f[n][1]) << endl;
    
    return 0;
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>