CF983（div2）(未补）

CF983（div2）

A. Circuit

题意：每盏灯有两个开关，每个开关有1个灯，一个开关打开灯就打开，两个开关打开灯就关闭，给定开关，求最少亮的灯泡和最多亮的灯泡

分析：如果开关的灯是奇数，那么至少有一个灯泡亮，否则没有灯泡亮。求最大的亮灯泡就是求开和关的匹配数

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){int n;cin>>n;int a[2*n+10];int c1=0,c0=0;for(int i=1;i<=2*n;i++){cin>>a[i];if(a[i]==1)c1++;else c0++;}if(c1%2==0)cout<<"0 ";else cout<<"1 ";cout<<min(c1,c0)<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0;
}
​

B - Medians

题意：给定一组数组，切割成m块，每次求出子数组的中位数，再将所有子数组的中位数求中位数，最后得到目标值k

分析：如果当前中位数在目标值的左边，就在左边找子数组，反之在右边

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll n,k;
void sol(){cin>>n>>k;ll s=(n+1)/2;//2if(n==1&&k==1){cout<<"1"<<endl;cout<<"1"<<endl;return;}if(k<=1||k>=n){cout<<"-1"<<endl;return;}if(s==k){cout<<n<<endl;for(int j=1;j<=n;j++)cout<<j<<" ";}else if(s>k){ll c=s-k;if(n-(2*c+1)<=0){cout<<"-1"<<endl;return;}cout<<n-(2*c+1)+1<<endl;for(int i=1;i<=n-(2*c+1)+1;i++){cout<<i<<" ";}}else{ll c=k-s;if(n-(2*c+1)<=0){cout<<"-1"<<endl;return;}cout<<n-(2*c+1)+1<<endl;cout<<1<<" ";for(int i=(2*c+1)+1;i<=n;i++){cout<<i<<" ";}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0;
}
​

C - Trinity

题意：给定数组a，可以进行任意次操作：选择i和j，ai=aj，使得最后数组，任选三个数都可以组成三角形，两数大于第三数

分析：每次找区间内任选三个都可以组成三角形，用二分找右区间，即可算出没有在区间内的

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){int n;cin>>n;ll a[n+10];for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);ll ans=0x3f3f3f3f3f3f3f;for(int i=1;i<=n;i++){ll l=i,r=n;while(l<r){ll mid=(l+r)/2;if(a[mid]>=a[i]+a[i+1])r=mid;else l=mid+1;}//不在区间的最小值 ll c;if(l==n){if(a[n]<a[i]+a[i+1]){//在区间 c=i-1;}else{c=i-1+1; }}else c=i-1+(n-l+1);ans=min(ans,c);}if(ans==0x3f3f3f3f3f3f3f)cout<<"0"<<endl;else cout<<ans<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0;
}
​