#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int _;
cin>>_;
while(_--){
int a[];int add=;
for(int i=;i<=;i++){
cin>>a[i];add+=a[i];
}
sort(a+,a++);
int sum1=;
int cha=a[]-a[];
if(a[]>=cha){
a[]-=cha;
int ans=;
ans=a[]+a[]/;
cout<<ans<<'\n';
}else{
cout<<min(a[]+a[],a[])<<'\n';
}
//cout<<sum<<'\n';
}
return ;
}
或者二分也行。
#include<bits/stdc++.h> using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f
signed main(){
int _;int a,b,c;
cin>>_;
while(_--){
cin>>a>>b>>c;
int ans=;
int l=;
int r=;
while(l<=r){
int mid=(l+r)/;
int sum=;
sum=min(a,mid)+min(b,mid)+min(c,mid);
if(sum>=*mid){
l=mid+;
ans=max(ans,mid);
}else{
r=mid-; }
}
cout<<ans<<'\n';
}
return ;
}
直接暴力就行。但是注意要先记录出现次数然后才能更改。要不然就没了QAQ
#include<bits/stdc++.h> using namespace std;
#define int long long
string str[];
map<string,int> mp;
bool cmp(string a,string b){
return a>b;
}
signed main(){
int _;
cin>>_;
while(_--){
int n;
mp.clear();
cin>>n;
int flag=;
int s=; for(int i=;i<n;i++){
cin>>str[i];
mp[str[i]]++; }
// sort(str,str+n,cmp); for(int i=;i<n;i++){ int F=;
if(mp[str[i]]>=){
for(int j=str[i].size()-;j>=;j--){
for(int k=;k<=;k++){
string temp;
temp=str[i];
temp[j]=k+'';
if(!mp[temp]){
mp[temp]++;
s++;
mp[str[i]]--;
str[i]=temp;
F=;
}
if(F){
break;
}
}
if(F){
break;
}
}
}
}
cout<<s<<'\n';
for(int i=;i<n;i++)
cout<<str[i]<<'\n';
}
return ;
}
一共有n块钱，k个人[n/k]块钱，向下取整。
现在给你n块钱，你不知道有多少人，输出每个人可能获得多少钱
其实就是找可行方案。【好像正规做法是数论分块】
题意没理解QAQ。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int _;
cin>>_;
while(_--){
int n;
cin>>n;
vector<int> ans;
map<int,int> mp;
ans.push_back();
for(int i=;i*i<=n;i++){
if(!mp[i])
ans.push_back(i);
mp[i]=;
if(!mp[n/i])
ans.push_back(n/i);
mp[n/i]=;
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<'\n';
for(int i=;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<'\n';
}
return ;
}思路：暴力并查集就行了。真的难受。
#include<bits/stdc++.h> using namespace std;
string str[];
int f[];
int n;
map<int,int> mp;
int getf(int v){
if(f[v]==v){
return f[v];
}else{
f[v]=getf(f[v]);
return f[v];
}
}
void merge(int u,int v){
int t1=getf(u);
int t2=getf(v);
if(t1!=t2){
f[t2]=t1;
}
}
void init(){
for(int i=;i<=n+;i++)
f[i]=i;
}
signed main(){
cin>>n;
init();
int ans=;
for(int i=;i<=n;i++){
cin>>str[i];
for(int j=;j<str[i].size();j++){
if(!mp[str[i][j]-'a']){
mp[str[i][j]-'a']=i;
}
}
}
for(int i=;i<=n;i++){
int F=;
for(int j=;j<str[i].size();j++){
if(i!=mp[str[i][j]-'a']&&F){
merge(i,mp[str[i][j]-'a']);
F=; }
}
}
for(int i=;i<=n;i++){
if(f[i]==i)
ans++;
// cout<<f[i]<<" ";
}
// cout<<'\n';
cout<<ans<<'\n';
return ;
}
【菜是原罪】