M. Triangle Construction

题目链接：Problem - 1906M - Codeforces

题目大意：给一个 n 边形， 每一个边上有a[ i ] 个点， 在此多边形上求可以连的三角形有多少个， 每个点只能用一次。

输入：

第一行是一个整数 N ( 3 ≤ N ≤ 200000 )。

下面一行由 N 个整数 ai ( 1 ≤ ai ≤ 2⋅1e9 组成。）

                                        数学， 贪心

1.三个点就可以连成一个三角形

2.三角形肯定不能在一条边上。 贪心：当最大数量的一条边上的点mx，mx * 2比其他边的数量的总和还要大， 那么贪心的想，该最大的一条边对每个三角形贡献两个点。

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n;cin >> n;i64 mx = 0;i64 sum = 0;for(int i=0; i<n; i++) {i64 t;cin >> t;mx = max(mx, t);sum += t;}if((sum - mx) * 2 <= mx) { //特殊情况cout << sum - mx << "\n";}else{cout << sum / 3 << "\n";//结论}return 0;
}

感谢你的观看与点赞， 欢迎大佬指正。