网易互联网 算法通用（网申批）30 100 100 60

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        long long a,b,c;
        cin >> a >> b >> c;
        long long avg = (a+b+c) / 3;
        long long sheng = (a+b+c) % 3;
        long long x=0,y=0,z=0;
        if(a+b < avg) x = avg-a-b;
        if(b+c < avg) y = avg-b-c;
        if(a+c < avg) z = avg-a-c;
        cout << avg+sheng/2+sheng%2<< endl;
    }
    return 0;
}

def isojbk(nums,m):
    m += nums[0]
    nums[0] = 0
    for i in range(1,len(nums)):
        if nums[i] >= i:
            m += nums[i] - i
            nums[i] = i
            continue
        if nums[i] < i and i - nums[i] > m:
            return False
        else:
            m -= (i-nums[i])
            nums[i] = i
            continue
    return True
t = int(input())
t2 = t
nm = []
nums = []
while t>0:
    nm.append(list(map(int,input().split())))
    nums.append(list(map(int,input().split())))
    t -=1
for i in range(t2):
    print('YES' if isojbk(nums[i],nm[i][1]) else 'NO')

#include<vector>
#include<iostream>
using namespace std;

string isok(int n, int k, vector<int> h)
{
 vector<vector<int>> dp(n, vector<int>(2, 0));
 dp[0][0] = 1;
 for (int i = 1; i < n; i++)
 {
  for (int j = i - 1; j >= 0 && j >= i - k; j--)
  {
   if (dp[j][0] && h[j] >= h[i]) //j没用  i也没用
   {
    dp[i][0] = 1;
   }
   if (dp[j][1] && h[j] >= h[i])//j用了 i没用
   {
    dp[i][1] = 1;
   }
   if (dp[j][0]) //j没用 i用
   {
    dp[i][1] = 1;
   }
  }
 }
 if (dp[n - 1][0] || dp[n - 1][1])
  return "YES";
 return "NO";
}

int main()
{
 int T;
 cin >> T;
 vector<string> ans;
 for (int i = 0; i < T; i++)
 {
  int n, k;
  cin >> n >> k;
  vector<int> h(n, 0);
  for (int i = 0; i < n; i++)
  {
   cin >> h[i];
  }
  ans.push_back(isok(n, k, h));
 }
 for (int i = 0; i < T; i++)
 {
  cout << ans[i] << endl;
 }
}

def insertion_sort(nums):
    d = [i for i in range(len(nums))]
    cout = 0
    for insertion_index in range(1, len(nums)):
        while insertion_index > 0 and nums[insertion_index] < nums[insertion_index -1]:
            cout += abs(d[insertion_index]-d[insertion_index - 1])
            d[insertion_index - 1], d[insertion_index] = d[insertion_index], d[insertion_index - 1]
            nums[insertion_index - 1], nums[insertion_index] = nums[insertion_index], nums[insertion_index - 1]
            insertion_index -= 1
    return cout
n = int(input())
nums = list(map(int,input().split()))
print(insertion_sort(nums))