A-似巨龙高歌
题意
对考试的名次重新排序,使得进步最大的进步名次最少。
思路
按照名次从小到大进行排序,这样保证了进步的名次最少,从而取进步的最大值。
代码
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
typedef long long ll;
const int N=1e7+9,mod=998244353;
int a[N],b[N];
void solve()
{
int n;
cin >> n;
for(int i = 1;i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int ans=INT_MIN;
for(int i = 1;i < n; i++){
ans = max(ans,a[i]-a[i+1]);
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// solve();
int T;
T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
题意
对于一个01数组,分别在1-n区间内对数组进行两次操作:1:将[1,i]内数字进行翻转 2:将[1,i]内的所对应的值进行反转(0变为1,1变为0)。
思路
模拟过程发现:当n为奇数时:a1,a2,a3,a4,a5-->!a5,!a3,!a1,a2,a4,即:原下标为奇数的取反逆序排列在前,原下标为偶数正序排列在后;当n为偶数时:a1,a2,a3,a4-->!a4,!a2,a1,a3,即:原下标为偶数的取反逆序排列在前,原下标为奇数的正序排列在后。
代码
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
typedef long long ll;
const int N=1e7+9,mod=998244353;
int a[N],b[N];
void solve()
{
int n;
cin >> n;
for(int i = 1;i <= n; i++) cin >> a[i];
int k = 1;
if(n & 1)
{
for(int i = n; i >= 1; i--){
if(i & 1){
if(a[i] == 1) b[k++] = 0;
else b[k++] = 1;
}
}
for(int i = 1; i <= n; i++){
if(i % 2 == 0){
b[k++] = a[i];
}
}
}
else
{
for(int i = n;i >= 1; i--){
if(i % 2 == 0){
if(a[i] == 1) b[k++] = 0;
else b[k++] = 1;
}
}
for(int i =1 ;i <= n; i++){
if(i & 1){
b[k++] = a[i];
}
}
}
for(int i = 1; i <= n; i++)
cout << b[i] << ' ';
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// solve();
int T;
T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
题意
在一条公路上有n个站点,已知每一个站点距离下一个站点的路程以及每个站点的油价,求解从第1个站点到达第n个站点时,最少的油费。
思路
到达一个站点时,肯定是由前一个站点加油而来,那么我们每个站点的油价等于自身与前一个站点的油价的最小值,这样保证了花费最少,并且每次都要判断到达该站点之后距离下一个站点的距离(可能上次所加的油还没有用完)。
代码
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
typedef long long ll;
const int N=1e6+9,mod=998244353;
ll b[N],a[N];
ll vis[N];
void solve()
{
int n,d;
cin >> n >> d;
for(int i = 1;i < n;i++)
cin >> a[i];//距离
for(int i = 1;i <= n;i++)
cin >> b[i]; //价钱
for(int i = 2;i <= n;i++)
b[i] = min(b[i-1],b[i]);
ll sum = 0,temp = 0;
for(int i = 1;i < n;i++){
temp += a[i]; //距离下一个点的距离
if(temp > 0){
sum += ((temp + d -1) / d) * b[i];
}
temp = temp - ((temp + d -1) / d) * d;
// cout << temp << '\n';
}
cout << sum << '\n';
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// solve();
int T;
T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
题意
一共有n个苹果,从第一个开始取,每隔两个取一个;随后苹果继续排序,第二天按照规则继续取,求解多少天能取完这n个苹果且第n个苹果是在第几天取走的。
思路
模拟发现,每次取的苹果都是下标除3余1的值,并且每天取得的苹果总数为(n + 3 - 1) / 3。
代码
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
typedef long long ll;
const int N=1e7+9,mod=998244353;
int a[N],b[N],vis[N];
void solve()
{
int n;
cin >> n;
int f = 0,cnt = 0;
while(n){
cnt++;
if(n == 0) break;
if(n % 3 == 1 && !f) f = cnt;
n -= (n + 3 - 1) / 3;
}
cout << cnt << " " << f << endl;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// solve();
int T;
T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}