数学与思维

一道数学题

题目的大致意思如下 :

你有 n种数字的卡片，数字为i的卡牌有ai张

你需要从中选出至少 3 张排成一个圆环（首尾相连），
使得对于圆环上任意连续的三张牌，其中至少有两张的数值相同。

问：最多可以选出多少张牌满足这个条件。

蒟蒻当时没有ac，后来仔细想想，挺好做的（蒟蒻只觉得当时头有点晕）废话不多说，开始：

我们很容易想到一下的搭配是合理的：

换句话说，我们需要形如AAB，AAA的样式结构，进一步，如果第i堆的卡牌数大于1，那么我们都可以选，接下来，我们统计牌堆数为1的个数（方便后面统计）,仔细思考我们可以发现，两个一样的可以和另一个不用的搭配，来使我们是结果最大化

但是

我们要注意出现如下图的情况

好的，我们来展示代码

voidsolve(){intn;cin>>n;intres=0;intcnt=0;vector<int>e;intcnt1=0;for(inti=1;i<=n;i++){intx;cin>>x;if(x>1){res+=x;cnt1++;e.push_back(x);}else{cnt++;}}intdis=0;for(intx:e){if(cnt1<2){dis+=x/2;}else{dis+=(x-2)/2;}}cnt=min(dis,cnt);res+=cnt;if(res<3){cout<<0<<"\n";}else{cout<<res<<"\n";}}