Rogue list - greedy

milk

Jump ！

#include <bits/stdc++.h> using namespace std; //  greedy ( Look for the largest and smallest jumps in the remaining stones ) //
https://www.luogu.com.cn/problem/P4995#submit int stone[100000]; int
main() {
      
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
      
        cin >> stone[i];
    }
    sort(stone + 1, stone + 1 + n);
    int rnode = n;
    int lnode = 0; // lnode  The initial value is 1！ Because at first on the ground 
    bool flag = true;
    long long ans = 0;
    while (lnode != rnode)
    {
      
        if (flag)
        {
      
            ans += (stone[rnode] - stone[lnode]) * (stone[rnode] - stone[lnode]);
            lnode++;
            flag = false;
        }
        else
        {
      
            ans += (stone[rnode] - stone[lnode]) * (stone[rnode] - stone[lnode]);
            rnode--;
            flag = true;
        }
    }
    cout << ans;
    return 0; } ```
###  Souvenir group  ![ Insert picture description here ](https://img-blog.csdnimg.cn/b467d16d231242078636be0d5e9cd2f9.png)

[ Portal ](https://www.luogu.com.cn/problem/P1094) ```cpp
#include <bits/stdc++.h> using namespace std; // https://www.luogu.com.cn/problem/P1094 int gift[100000]; int main()
{
      
    int m, n, cnt;
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
      
        cin >> gift[i];
    }
    sort(gift + 1, gift + 1 + n);
    int rnode = n;
    int lnode = 1;
    cnt = 0;
    while (lnode < rnode)
    {
      
        if (gift[lnode] + gift[rnode] <= m)
        {
      
            cnt++;
            lnode++, rnode--;
        }
        else
        {
      
            rnode--;
            cnt++;
        }
    }
    if (lnode == rnode)
    {
      
        cnt++;
    }
    cout << cnt;
    return 0; } ```
###  Three Kingdoms game  ![ Insert picture description here ](https://img-blog.csdnimg.cn/801c46d9cbc34e2bae816890c413a3d9.png)
![ Insert picture description here ](https://img-blog.csdnimg.cn/af32c24f09c94d45a4da06045614f5f7.png)
![ Insert picture description here ](https://img-blog.csdnimg.cn/77064a078bdc445287c1e275e2b16e73.png)
[ Portal ](https://www.luogu.com.cn/problem/P1199) ```cpp
#include <bits/stdc++.h> using namespace std; int gen[10000][10000]; //  greedy + Game theory  //  Choose the second largest one each time ！ int main() {
       
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
      
        for (int j = i + 1; j <= n; j++)
        {
      
            cin >> gen[i][j];
            gen[j][i] = gen[i][j];
        }
    }
    int ans = -1;
    for (int i = 1; i <= n; i++)
    {
      
        sort(gen[i] + 1, gen[i] + 1 + n, greater<int>());
        ans = max(ans, gen[i][2]);
    }
    cout << 1 << endl;
    cout << ans << endl;
    return 0; } ```
###  salesman 

![ Insert picture description here ](https://img-blog.csdnimg.cn/32d69d1293bb4f11ade9082c00ca3f6a.png)
![ Insert picture description here ](https://img-blog.csdnimg.cn/a5c8b741d1a54e84a05120619d642889.png)
[ Portal ](https://www.luogu.com.cn/problem/P2672) ```cpp
#include <bits/stdc++.h> using namespace std; // https://www.luogu.com.cn/problem/P2672 int N; struct node {
       
    int dis;
    int tire; } a[100000]; int t[100000];    // t[i] On behalf of i Prefix of maximum fatigue value and  int d[100000]; // q[i] On behalf of i The fatigue value spent in distance among users with the highest fatigue value  int post[100000];
// post[i] Delegate pick i After users with the maximum fatigue value , The maximum value left  bool cmp(node a, node b) {
      
    return a.tire > b.tire; } int main() {
      
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
      
        cin >> a[i].dis;
    }
    for (int i = 1; i <= N; i++)
    {
      
        cin >> a[i].tire;
    }
    sort(a + 1, a + 1 + N, cmp);
    for (int i = 1; i <= N; i++)
    {
      
        t[i] = t[i - 1] + a[i].tire;
    }
    for (int i = 1; i <= N; i++)
    {
      
        d[i] = max(d[i - 1], a[i].dis * 2);
    }
    for (int i = N; i >= 1; i--)
    {
      
        post[i] = max(post[i + 1], 2 * a[i].dis + a[i].tire);
    }
    for (int i = 1; i <= N; i++)
    {
      
        cout << max(t[i] + d[i], t[i - 1] + post[i]) << endl;
    }
    return 0; } ```