Question A
Meaning: give you 2*n numbers, let you provide a sequential ring, so that 2An= An-1 +An+1
Solution:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e5+50; inline int read(){ int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data*w; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T;cin>>T; while(T--){ int n;cin>>n;n*=2; int a[60]; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ cin>>a[i]; }sort(a+1,a+1+n); int b[60]; memset(b,0,sizeof(b)); for(int i=1;i<=n/2;i++){ b[i*2-1]=a[i]; } int pos=n; for(int i=1;i<=n/2;i++){ b[i*2]=a[pos--]; } for(int i=1;i<=n;i++){ cout<<b[i]<<" "; }cout<<endl; } return 0; }
Question B
Question meaning: judge whether a number can be composed of 111111111... 11111111
Idea: first of all, 1111 can be composed of 11, which can be introduced into the scope of 1e9. We only need to judge whether it can be composed of 11111111111111111. At first, we didn't dare to knock violence and felt T, but there was no better way for a while, so we made a mess (FOG)
Problem solution
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e5+50; inline int read(){ int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data*w; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T;cin>>T; while(T--){ ll n;cin>>n; bool f=0; int q1=n/1111111,q2=n/11111,q3=n/111; for(int i=q1;i>=0;i--){ int las=(n-i*1111111)/11111; for(int j=las;j>=0;j--){ int lss=(n-i*1111111-j*11111)/111; for(int k=lss;k>=0;k--){ int lsss=n-i*1111111-j*11111-k*111; if(lsss%11==0){ f=1; break; } } if(f)break; } if(f)break; } if(f)cout<<"YES"<<endl; else { cout<<"NO"<<endl; } } return 0; }
Question C (C1 n < 2000 C2 n < 200000)
Question meaning: you have a life value of h=0, and then you have n bottles of potions, which can add blood or deduct blood. Ask how many bottles of potions you can drink at most in the order from left to right. You need to keep H > = 0 in the whole process;
Idea: O (n)
First of all, we can think that the problem of this question is how to consider 9-9-1-1. In this case, we must drink up to four bottles. At the beginning, our brain suddenly thought of dp, which is a bit like a backpack.
But think about it carefully. Greed can be solved. In fact, we only need to judge what operation we can use to replace - 1 with - 9 when we encounter - 1, that is, we have to record the used potion that will deduct blood, and replace the one who has drunk the most blood in front, so the priority queue of dadingdui is very clear.
First, at first, h=0,
- If H + a [i] > = 0, ans + +, then throw the potion (it doesn't matter whether it's positive or negative, and it doesn't affect the answer) into the priority queue;
- If the current a[i] + H is less than 0, then we can judge the team leader and the current medicine who withholds more blood. If the team leader withholds more blood (if a[i] withholds more blood, it will not be updated), pop the team leader and add a[i], h=h-q.top()+a[i], to update the healthier blood volume.
Problem solution
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1e5+50; inline int read(){ int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data*w; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n;cin>>n; ll h=0,ans=0; priority_queue<ll,vector<ll>,greater<ll> >q; for(int i=1;i<=n;i++){ ll temp;cin>>temp; if(temp+h>=0){ ans++; h+=temp; q.push(temp); } else { if(!q.empty()&&q.top()<temp){ h=h-q.top()+temp; q.pop(); q.push(temp); } } // cout<<h<<endl; } cout<<ans<<endl; return 0; }
It's A pity that question C was thought of at the end of the game