A. Payment Without Change
#include<bits/stdc++.h> using namespace std;
#define int long long
#define N 100500
int arr[N];
signed main(){
int _;
cin>>_;
while(_--){
int a,b,n,s;
cin>>a>>b>>n>>s;
int y=s/n;
int x=min(a,y);
s-=x*n;
if(b>=s){
printf("YES\n");
} else{
printf("NO\n");
}
}
return ;
}
B. Minimize the Permutation
按照题意暴力就行。从1到n枚举，每个数尽量地往前和比他大的数交换。并且保证相邻的位置只能换一次。【比赛·的时候读错题意，还想错了思路QAQ难受====】
#include<bits/stdc++.h> using namespace std;
#define int long long
#define N 150
int arr[N];int vis[N];
signed main(){
int _;
cin>>_;
while(_--){ int n;cin>>n;
for(int i=;i<=n;i++)
cin>>arr[i];
int m=n-;
while(){
int flag=;
for(int i=n-;i>=;i--){
if(vis[i])
continue;
if(arr[i]>arr[i+]){
int t=arr[i];
arr[i]=arr[i+];
arr[i+]=t;
m--;
flag=;
vis[i]=;
if(m<=){
break;
}
}
}
if(m<=){
break;
}
if(!flag){
break;
}
}
for(int i=;i<=n;i++){
printf("%lld ",arr[i]);
} printf("\n");
for(int i=;i<=n+;i++)
arr[i]=vis[i]=;
}
return ;
}
C. Platforms Jumping（贪心）【补题】
贪心：在板之间加水。这样保证了所有的板都用上了。最后再特盘一个不能到达的情况即可。开始模拟。【这题调了一会BUG，好久没刷题的，代码都打不清楚了QAQQAQQAQ】
#include<bits/stdc++.h> using namespace std;
#define int long long
#define N 150000
int arr[N];int n,m,k;
int c[N];
struct str{
int id;
int length;
}st[N]; signed main(){
cin>>n>>m>>k;
int Sum=;
int POS=;
for(int i=;i<=m;i++){
POS+=k;
scanf("%lld",&st[i].length);
st[i].id=i;
POS+=st[i].length-;
Sum+=st[i].length;
}
POS+=k;
if(POS<n+){
printf("NO\n");
return ;
}
printf("YES\n");
int tot=n-Sum;
int flag=;
int dis=k-;int now=;
int pos=;
//out<<tot<<endl;
for(int i=;i<=m;i++){
if(flag==){
int temp=min(dis,tot);
tot-=temp;
if(tot<=){
flag=;
}
while(temp--)
arr[++now]=;
temp=st[i].length;
// Sum-=temp;
while(temp--)
arr[++now]=i;
}else{
int _;_=st[i].length;
while(_--)
arr[++now]=i;
}
if(now>=n+){
break;
}
}
for(int i=;i<=n;i++)
cout<<arr[i]<<" ";
printf("\n"); return ;
}
D. Binary String Minimizing（贪心）
从左到右每个0依次和当前最左边的1交换，消耗这两个数下标之差的交换次数。
如果次数不够用，就让这个0和最远的能交换的1交换位置。
直接模拟就行。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int _;
cin>>_;
while(_--){
int left=;
int n,m;cin>>n>>m;string str;cin>>str;
for(int i=;i<str.size();i++){
if(str[i]==''){
left=i;
break;
}
}
for(int i=;i<str.size();i++){
if(str[i]==''&&i!=){
while(str[left]!=''&&left<str.size())
left++;
if(left<i){ if(m>=(i-left)){
m-=(i-left);
str[left]='';
str[i]='';
}else{
str[i-m]='';
str[i]='';
m=;
}
if(m<=){
break;
}
}
}
}
cout<<str<<endl;
}
return ;
}
用vector记录0的位置，然后模拟
#include<bits/stdc++.h> using namespace std;
#define int unsigned long long
#define N 1000500
int vis[N];
vector<int> v;
signed main(){
int _;
cin>>_;
while(_--){
int n,m;
cin>>n>>m;string str;
v.clear();cin>>str;
int left=;
int sum0=;int sum1=;
for(int i=;i<str.size();i++){
if(str[i]==''){
if(m>=(i-left)){
m-=(i-left);
sum0++;
left++;
}else{ if(m){
v.push_back(i-m);m=;
}else{
v.push_back(i);
}
}
}else{
sum1++;
}
}
int len=v.size();
for(int i=;i<sum0;i++){
cout<<"";
}int cnt=;
for(int i=sum0;i<n;i++){
if(cnt<len){
if(v[cnt]==i){
cout<<"";
cnt++;
}else{
cout<<"";
}
}else{
cout<<"";
}
}
printf("\n"); }
return ;
} /*
11011010
01111010
*/
E,F待补。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
一场掉了分的DIV3。。。