A. Kids Seating
题目大意:
给你一个n，从1~4n中选出n个数字使得数字两两gcd≠1并且不能互相整除
思路:
考虑从4n往前取，每次减少2，即可使得两两之间的gcd=2
同时，由4n取到2n，所以两两之间也不可整除
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n;
void solve(){
cin>>n;
for(int i=4*n; i>2*n; i-=2)cout<<i<<" ";
putchar('\n');
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
B. Saving the City
题目大意:
给你一个01字符串s，消除其中连续的1耗费a，将一个0变为1耗费b，求将整个字符串s全部变成0所消耗的最小值
思路:
取将不相连的两段相连与否的最小值即可，即为
第一个连续的1直接耗费a，后面记录到下一段的1的距离（即为中间0的个数），然后m i n ( s u m ∗ b , a ) min(sum*b,a)min(sum∗b,a)即可
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int a, b, ans;
string s;
void solve(){
cin>>a>>b;
cin>>s;
ans=0;
int flag=0, sum=0;
for(int i=0; i<s.length(); i++){
if(s[i]=='1'){
if(!flag) flag=1, ans=a;
else ans+=min(a,sum*b);
sum=0;
}
if(s[i]=='0') sum++;
}
cout<<ans<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
C. The Delivery Dilemma（贪心|二分）
题目大意:
共有n道菜，餐厅给你送过来的时间为ai ，你自己去餐厅拿的时间为bi ，不同的餐厅可以同时送餐，但在一段时间内你只能去一家餐厅
求n道菜全部到家的最小时间
思路1:
考虑二分答案，首先假设自己去所有的餐厅取餐，然后二分答案，当前时间大于mid时，自己去取餐，小于mid的让餐厅送过来，算出自己去拿的时间然后与当前的时间mid作判断
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, a[N], b[N];
int l, r, mid, sum;
bool check(int x){
sum=0;
for(int i=1; i<=n; i++)
if(a[i]>x)
sum+=b[i];
return sum<=x;
}
void solve(){
l=r=0;
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i], r+=b[i];
while(l<r){
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
思路2:
考虑将各个菜的时间按照a aa非递增排序，然后前缀和维护b bb的送餐时间，然后a n s = m i n ( a n s , m a x ( s u m [ i − 1 ] , a [ i ] ) ) ans=min(ans,max(sum[i-1], a[i]))ans=min(ans,max(sum[i−1],a[i]))
很好理解的思路，就不说了
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, sum[N];
struct node
{
int a, b;
}tim[N];
bool cmp(node a, node b){
if(a.a==b.a) a.b<a.b;
return a.a>b.a;
}
void solve(){
cin>>n;
for(int i=1; i<=n; i++) cin>>tim[i].a;
for(int i=1; i<=n; i++) cin>>tim[i].b;
sort(tim+1,tim+1+n,cmp);
for(int i=1; i<=n; i++) sum[i]=sum[i-1]+tim[i].b;
int ans=INF;
tim[n+1].a=0;
for(int i=n+1; i>=1; i--){
ans=mymin(ans,max(sum[i-1], tim[i].a));
}
cout<<ans<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
Comments | NOTHING