网站备案 网站,网站开发文档网站,我们做的网站是优化型结构,百度网站改版题目链接#xff1a;Problem - 1906M - Codeforces
题目大意#xff1a;给一个 n 边形#xff0c; 每一个边上有a[ i ] 个点#xff0c; 在此多边形上求可以连的三角形有多少个#xff0c; 每个点只能用一次。
输入#xff1a;
第一行是一个整数 N ( 3 ≤ N ≤ 200000…题目链接Problem - 1906M - Codeforces
题目大意给一个 n 边形 每一个边上有a[ i ] 个点 在此多边形上求可以连的三角形有多少个 每个点只能用一次。
输入
第一行是一个整数 N ( 3 ≤ N ≤ 200000 )。
下面一行由 N 个整数 ai ( 1 ≤ ai ≤ 2⋅1e9 组成。 数学 贪心
1.三个点就可以连成一个三角形
2.三角形肯定不能在一条边上。 贪心当最大数量的一条边上的点mxmx * 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 i0; in; 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;
}感谢你的观看与点赞 欢迎大佬指正。
