拼多多笔试代码 2023.10.08
第一题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1e5+5;
int k[N],l[N];
int main(){
int n;cin>>n;
for(int i=0;i<n;i++)cin>>k[i];
for(int i=0;i<n;i++)cin>>l[i];
sort(k,k+n);
sort(l,l+n);
int le,ri;
le=ri=0;
int ans=0;
while(le<n&&ri<n){
if(k[le]>l[ri]){
le++;
ri++;
ans++;
}else{
le++;
}
}
cout<<ans<<endl;
}
第二题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1005;
ll w[N],sum[N];
int main(){
// cout<<256.0/(988+100+132)<<endl;
int t;cin>>t;
while(t--){
memset(w,0,sizeof(w));
memset(sum,0,sizeof(sum));
int n,k;cin>>n>>k;
double use_temp=k*0.01;
for(int i=0;i<n;i++){
cin>>w[i];
if(i==0)sum[i]=w[i];
else sum[i]=sum[i-1]+w[i];
}
ll ans=0;
for(int i=1;i<n;i++){
sum[i-1]+=ans;
double temp=w[i]*1.0/(sum[i-1]*1.0);
// cout<<temp<<endl;
if(temp<use_temp){
continue;
}else{
double kk=(w[i]*1.0)/use_temp;
int x=kk;
double y=kk-x;
if(y>0){
x++;
}
ans+=(x-sum[i-1]);
}
}
cout<<ans<<endl;
}
}
第三题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#define ll long long
using namespace std;
queue<string>q,q2,q3,q4,q5,q6;
int main(){
int t;cin>>t;
while(t--){
int m;
string s;
ll ans=0;
cin>>m>>s;
while(!q.empty())q.pop();
while(!q2.empty())q2.pop();
while(!q3.empty())q3.pop();
while(!q4.empty())q4.pop();
while(!q5.empty())q5.pop();
while(!q6.empty())q6.pop();
q.push(s);
while(!q.empty()){
string temp=q.front();q.pop();
string son="";
for(int i=0;i<temp.length();){
if(i+2<temp.length()){
if(temp[i]=='P'&&temp[i+1]=='D'&&temp[i+2]=='D'){
ans++;
if(son!=""){
q2.push(son);
}
son="";
i+=3;
}else{
son+=temp[i];
i++;
}
}else{
son+=temp[i];
i++;
}
}
if(son!=""){
q2.push(son);
}
}
// while(!q2.empty()){
// if(m<=0)break;
// string temp=q2.front();q2.pop();
// string son="";
// for(int i=0;i<temp.length();){
// if(i+2<temp.length()){
// if(temp[i]=='P'&&temp[i+2]=='D'){
// if(m<=0)break;
// else{
// ans++;
// m--;
// }
// if(son!=""){
// q3.push(son);
// }
// son="";
// i+=3;
// }else{
// son+=temp[i];
// i++;
// }
// }else{
// son+=temp[i];
// i++;
// }
// }
// if(son!=""){
// q3.push(son);
// }
// }
while(!q2.empty()){
if(m<=0)break;
string temp=q2.front();q2.pop();
string son="";
for(int i=0;i<temp.length();){
if(i+1<temp.length()){
if((temp[i]=='P'&&temp[i+1]=='D')||(temp[i]=='D'&&temp[i+1]=='D')){
if(m<=0)break;
else{
ans++;
m--;
}
if(son!=""){
q4.push(son);
}
son="";
i+=2;
}else{
son+=temp[i];
i++;
}
}else{
son+=temp[i];
i++;
}
}
if(son!=""){
q4.push(son);
}
}
while(!q4.empty()){
if(m<=1)break;
string temp=q4.front();q4.pop();
string son="";
for(int i=0;i<temp.length();){
if(temp[i]=='P'||temp[i]=='D'){
if(m<=1)break;
else{
ans++;
m-=2;
}
if(son!=""){
q5.push(son);
}
son="";
i++;
}else{
son+=temp[i];
i++;
}
}
if(son!=""){
q5.push(son);
}
}
ans+=(m/3);
cout<<ans<<endl;
}
}
第四题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#define ll long long
using namespace std;
const int N = 1e5+5;
ll k[N];
ll val[N];
ll sum;
ll n,t;
void dfs(int pos,ll weigh,int step){
val[pos]=min(val[pos],weigh);
for(int i=0;i<=step;i++){
if(k[1+i+pos]+val[pos]>t)continue;
if(1+i+pos>n)continue;
if(k[1+i+pos]+val[pos]<val[1+i+pos])
dfs(1+i+pos,k[1+i+pos]+val[pos],step);
}
}
ll solve(int step){
for(int i=0;i<=step;i++){
// cout<<1+i<<' '<<k[1+i]<<' '<<step<<endl;
if(k[1+i]>t)continue;
if(1+i>n)continue;
dfs(1+i,k[1+i],step);
}
ll target_val=sum+1;
// cout<<step<<' ';
for(int i=n;i>=n-step;i--){
// cout<<val[i]<<' ';
target_val=min(target_val,val[i]);
}
// cout<<endl;
// cout<<"adsa "<<step<<' '<<target_val<<endl;
return target_val;
}
int erfen(int le,int ri){
int mid=(le+ri)>>1;
while(le<ri){
for(int i=0;i<=n;i++){
val[i]=sum+1;
}
// cout<<mid<<endl;
// cout<<solve(mid)<<' ';
if(solve(mid)<=t){
ri=mid;
}else{
le=mid+1;
}
// cout<<le<<' '<<ri<<endl;
mid=(le+ri)>>1;
}
if(solve(mid)>t){
le=le-1;
}
return le;
}
int main(){
int T;cin>>T;
while(T--){
memset(k,0,sizeof(k));
cin>>n>>t;
sum=0;
for(int i=1;i<=n;i++){
cin>>k[i];
sum+=k[i];
}
if(sum<=t){
cout<<0<<endl;
}else{
int ans=erfen(1,n);
cout<<ans<<endl;
}
}
}
快手开奖113人在聊