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;
}
感谢你的观看与点赞， 欢迎大佬指正。