AcWing周赛第59场总结

一、4491.数组操作

1、原题链接:4491.数组操作

2、解题思路:

计算出数组元素之和和最小前缀和,然后相减即可。

详情见代码。

3、参考代码:

#include 
using namespace std;

const int N = 110;
int a[N], s[N];

int main()
{
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    int r = 0;
    for (int i = 1; i <= n; i ++) {
        s[i] = s[i - 1] + a[i];
        r += a[i];
    }
    
    sort(s + 1, s + n + 1);
    int x = min(0, s[1]);
    
    cout <

二、4492.减去操作

1、原题链接:4492.减去操作

2、解题思路:

【1】奇数的最小质因子一定是奇数

【2】偶数的最小质因子一定是2

第一步,判断n的奇偶性;

第二步,若n为偶数,参考【2】,那么操作次数一定就是n/2;

第三步,若n为奇数,参考【1】,找到其最小质因子然后减去,再进行第二步操作即可。

3、参考代码:

#include 

using namespace std;

typedef long long ll;

int main()
{
    ll n;
    cin >> n;
    
    ll res = 0;
    //若n为奇数,则找到它的最小质因子,并减去
    if(n % 2)
    {
        for(int i = 2; i <= n / i; i ++ )
        {
            if( n % i == 0){
                n -= i;
                res ++;
                break;
            }
        }
        //特判,若n仍为一个质数,那么它本身就是一个质因子。
        if(n % 2) res ++, n = 0;
    }
    
    res += n / 2;
    cout << res << endl;
    
    return 0;
}

你可能感兴趣的