Edu176-C. Two Colors · znzryb

## 思路讲解

难点在于怎么把这个双循环搞成单循环

![image](https://media.znzryb.com/20250317-922a9c84/image_edd75e17.png)

然后记得读题，那个栅栏仅能由两种颜色构成，多了，少了都不行。

## AC代码

这个+2也是比较迷，但加了就AC了，我也不知道为什么。

可能是原来比16还要多减一次1，但其实和16一样。

[https://codeforces.com/contest/2075/submission/311344453](https://codeforces.com/contest/2075/submission/311344453)

```cpp
// Problem: C. Two Colors
// Contest: Codeforces - Educational Codeforces Round 176 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2075/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN],sumA[MAXN];

inline void solve(){
	cin>>N>>M;
	// ll maxA=0;
	FOR(i,1,M){
		cin>>A[i];
	}
	sort(A+1,A+1+M);
	
	sumA[0]=0;
	FOR(i,1,A[M]){
		ll idx=M-(lower_bound(A+1,A+1+M,N-i)-A)+1;
		if(i==N){
			idx=0;
		}
		sumA[i]=sumA[i-1]+idx;
	}
	ll ans=0;
	// FOR(i,1,M){	// 暴力法存档
		// FOR(j,1,A[i]){
			// ll idx=M-(lower_bound(A+1,A+1+M,N-j)-A)+1;
			// if(N-j<=A[i]){
				// idx-=1;
			// }
			// if(j==N){
				// idx=0;
			// }
			// ans+=idx;
		// }
	// }
	FOR(i,1,M){
		ans+=sumA[A[i]];
		// if(A[i]==N){
			// if((A[i]-(N-A[i])+1)>0){
				// ans-=(A[i]-(N-A[i])+1);
			// }			
		// }else{
		if((A[i]-(N-A[i])+1)>0){
			ans-=(A[i]-(N-A[i])+1);
		}			

		if(A[i]>=N){
			ans+=2;
		}
	}	
// #ifdef LOCAL
	// FOR(i,1,A[M]){
		// cerr<<sumA[i]<<" ";
	// }
	// cerr<<"\n";
// #endif
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
#ifdef LOCAL
    cerr <<  '\n';
#endif
	}
	return 0;
}
/*

*/
```

## 心路历程（WA，TLE，MLE……）