#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int sum[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
a[i]=x;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
if(n%2==0){
printf("0 %d",sum[n]-2*sum[n/2]);
}
else{
printf("1 %d",max(abs(sum[n]-2*sum[n/2]),abs(sum[n]-2*sum[n/2+1])));
}
return 0;
}
活动打卡代码
AcWing 1603. 整数集合划分
活动打卡代码
AcWing 1517. 是否加满油
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
struct P{
double dis,pri;
}st[N];
bool cmp(P a,P b){
if(a.dis!=b.dis)
return a.dis<b.dis;
else
return a.pri<b.pri;
}
int main()
{
int c,d,da,n;
cin>>c>>d>>da>>n;
for(int i=0;i<n;i++){
double pri,dis;
cin>>pri>>dis;
st[i]={dis,pri};
}
st[n]={d*1.0,0};
sort(st,st+n+1,cmp);
if(st[0].dis!=0){
printf("The maximum travel distance = 0.00");
return 0;
}
double pet=0;//油量
double pri=0;//价钱
for(int i=0;i<n;){
int k=-1;
int flag=0;//是否有油价更便宜的站点
for(int j=i+1;j<n+1;j++){
if(st[j].dis-st[i].dis>c*da){
break;
}
if(st[j].pri<st[i].pri){
flag=1;
k=j;
break;
}
else if(k==-1||st[j].pri<st[k].pri){
k=j;
}
}
if(k==-1){
printf("The maximum travel distance = %.2lf",st[i].dis+1.0*c*da);
return 0;
}
else{
double temp=(st[k].dis-st[i].dis)/da;//这一段路程花的油量
if(flag){
double cost=temp-pet;//这一段需要加的油量
pri+=cost*st[i].pri;
i=k;
pet=0;
}
else{
pri+=(c-pet)*st[i].pri;
pet=c-temp;
i=k;
}
}
}
printf("%.2lf",pri);
return 0;
}
活动打卡代码
AcWing 1618. 结绳
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
a[i]=x;
}
sort(a,a+n);
double sum=a[0];
for(int i=1;i<n;i++){
sum=(sum+a[i])/2;
}
printf("%.0lf",floor(sum));
return 0;
}
活动打卡代码
AcWing 1556. 月饼
```
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
typedef long double ld;
const int N=1010;
struct P{
ld a,b,c;
}st[N];
bool cmp(P a,P b){
return a.c>b.c;
}
int main(){
int n,m;
cin>>n>>m;
m=1000;
ld x;
for(int i=0;i<n;i++){
scanf(“%Lf”,&x);
st[i].a=x1000;
}
for(int i=0;i<n;i++){
scanf("%Lf",&x);
st[i].b=x*1000;
}
for(int i=0;i<n;i++){
ld temp=st[i].b/st[i].a;
st[i].c=temp;
}
sort(st,st+n,cmp);
ld sum=0;
int k=0;
while(m>0&&k[HTML_REMOVED]=st[k].a)
sum+=st[k].b,m-=st[k].a,k++;
else
sum+=m*st[k].c,m-=m;
}
printf(“%.2Lf”,sum/1000+1e-18);
return 0;
}`
````
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
a[x]=i;
}
int res=0;
for(int i=1;i<n;i++){
while(i<n&&a[0]!=0)swap(a[0],a[a[0]]),res++;
while(i<n&&a[i]==i)i++;
if(i<n)swap(a[0],a[i]),res++;
}
cout<<res;
return 0;
}
图论，并查集相关
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
a[x]=i;
}
int res=0;
for(int i=1;i<n;i++){
while(i<n&&a[0]!=0)swap(a[0],a[a[0]]),res++;
while(i<n&&a[i]==i)i++;
if(i<n)swap(a[i],a[0]),res++;
}
cout<<res;
return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<string>res;
bool cmp(string a,string b){
return a+b<b+a;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
string s;
cin>>s;
res.push_back(s);
}
sort(res.begin(),res.end(),cmp);
int flag=0;
/* for(int j=0;j<res.size();j++){
for(int i=0;i<res[j].size();i++){
if(!flag&&res[j][i]=='0'){
continue;
}
else{
flag=1;
cout<<res[j][i];
}
}
}
if(flag==0&&res.size()!=0){
cout<<0;
}*/
string ans;
for(int i=0;i<res.size();i++){
ans+=res[i];
}
while(ans.size()>1&&ans[0]=='0')ans=ans.substr(1,ans.size()-1);
cout<<ans;
return 0;
}
活动打卡代码
AcWing 1522. 排成最小的数字
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<string>res;
bool cmp(string a,string b){
return a+b<b+a;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
string s;
cin>>s;
res.push_back(s);
}
sort(res.begin(),res.end(),cmp);
int flag=0;
for(int j=0;j<res.size();j++){
for(int i=0;i<res[j].size();i++){
if(!flag&&res[j][i]=='0'){
continue;
}
else{
flag=1;
cout<<res[j][i];
}
}
}
if(flag==0&&res.size()!=0){
cout<<0;
}
return 0;
}
活动打卡代码
AcWing 1521. 魔术卷
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int main(){
int n,m;
cin>>n;
vector<int>cz,cf,wz,wf;
for(int i=0;i<n;i++){
int x;
cin>>x;
if(x>0){
cz.push_back(x);
}
else
cf.push_back(abs(x));
}
cin>>m;
for(int i=0;i<m;i++){
int x;
cin>>x;
if(x>0){
wz.push_back(x);
}
else
wf.push_back(abs(x));
}
sort(cz.begin(),cz.end(),greater<int>());
sort(cf.begin(),cf.end(),greater<int>());
sort(wz.begin(),wz.end(),greater<int>());
sort(wf.begin(),wf.end(),greater<int>());
int sum=0;
for(int i=0;i<cz.size()&&i<wz.size();i++){
sum+=cz[i]*wz[i];
}
for(int i=0;i<cf.size()&&i<wf.size();i++){
sum+=cf[i]*wf[i];
}
cout<<sum;
return 0;
}
活动打卡代码
AcWing 1646. 谷歌的招聘
#include<iostream>
using namespace std;
bool isprime(int x){
if(x==1)return false;
for(int i=2;i<=x/i;i++){
if(x%i==0){
return false;
}
}
return true;
}
int main(){
int n,m;
cin>>n>>m;
string s;
cin>>s;
string temp;
for(int i=0;i+m<=s.size();i++){
temp=s.substr(i,m);
int x=atoi(temp.c_str());
if(isprime(x)){
cout<<temp;
return 0;
}
}
cout<<"404";
return 0;
}
