iT邦幫忙

0

[一天至少一題直到ICPC開賽002]解題:Theofanis' Nightmare(12/11)

  • 分享至 

  • xImage
  •  

Theofanis' Nightmare

題目連結
只要大於0就直接拆開,這就是貪心演算法

解題核心
本次用到貪心演算法
如果右邊的值>0,那麼他乘以越高位值(將陣列拆成越多塊)得出的值也越大
相反,如果最左邊的值<0,那麼就將其跟次位相加至>0就可以開始


因為用乘的會RE,所以用加法的(原理相同)


a*3==a+a+a
利用這個原理==>只要從陣列後面加入且值大於>0就加入ans等同於1(加第二次就是2)

可以舉下列例子:
1 2 3 -4 5
利用貪心
第一筆:5>0 ==>放入ans(目前:5)
第二筆:5+(-4)=1>0 ==>放入ans(5+1)
第三筆:1+3=4>0 ==>放入ans(4+6)
第四筆:4+2=6>0 ==>放入ans(10+6)
第五筆:6+1=7>0 ==>放入ans(16+7=23)

就等同於:
1(加一次)+2(加兩次)*2+3(加三次)*3-4(加四次)*4+5(加五次)*5
1+2 *2 + 3*3- 4* 4+5*5=23

```cpp
#include <iostream>
#include <vector>
#define ll long long int
#define dasabi uint

using namespace std;

/*
//* 題目:Theofanis' Nightmare
    題目連結:https://codeforces.com/contest/1903/problem/C
    解題者:神里綾華的狗(dasabi7414)
    使用語言:C++11
    本次技巧:Greedy
    解題連結:https://github.com/archie0732/c-solution/blob/main/codeforce/Theofanis'%20Nightmare.md
    本文會放在IT幫忙
//* 備註:本題是使用"貪心演算法"請先確保已經熟悉!!
*/


int main(int argc, char const *argv[])
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];

        // 這裡一定要用long long(因為我被搞過XD)
        ll sum = 0;
        ll ans = 0;
        // 倒著回來加
        for (int i = n - 1; i >= 0; i--)
        {
            // 如果相加大於0==>加入解答,反之==>繼續加(至其倒陣列坐左邊或sum>0)
            sum = v[i] + sum;
            if (sum > 0 || i == 0)
            {
                ans += sum;
            }
        }
        cout << ans << endl;
    }

    return 0;
}
// 總之,要先熟悉貪心演算法(Greedy),與多點的練習。
// 用乘法可會一直RE是正常的嗎
    

    
    

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言