突然发现星期三要讲课我日
TM为什么省选讲课这么神的东西要我来啊（虽然讲的只是贪心= =）
不多说了做贪心去了
裸的大贪心-。-
判断一下离a远还是离z远就可以了
（其实我只是打着找课件题目的幌子在刷水题(✿◡‿◡) ）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
int n,k;
char s[100005];
int main(){
n=IN(),k=IN();
gets(s+1);
Rep(i,1,n){
if (!k) break;
if ('z'-s[i]>s[i]-'a'){
int dist=min('z'-s[i],k);
s[i]+=dist,k-=dist;
}
else{
int dist=min(s[i]-'a',k);
s[i]-=dist,k-=dist;
}
}
if (!k) puts(s+1);else puts("-1");
}
首先把加油站按X排序。
$O(n)$处理出每个加油站右边离它最近而且价格小于等于它的加油站的标号，记为$sml_i$。然后按顺序从左往右走，每到一个加油站把油补充为$min(N,d)$就可以了。其中 $d=X_{sml_i}-X_i$。
证明：如果$d<N$,那么应该直接行驶到那个价格不比它高的加油站补充油，这样花费比较少；如果$d>N$，说明在后面距离为N的路程内必须要买更贵的油，那么应该直接把油箱补充满，这样在后面遇到价格高的加油站可以少买一点，花费也比较少。
时间复杂度$O(MlgM)$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) Out(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int M=200005;
struct Stat{
int x,p;
bool operator <(const Stat&w)const{return x<w.x;}
}a[M];
int d,n,m,sml[M];
int main(){
d=IN(),n=IN(),m=IN();
Rep(i,1,m) a[i].x=IN(),a[i].p=IN();
a[0].x=0;a[m+1].x=d;a[m+1].p=0;
sort(a+1,a+m+1);
sml[m]=m+1;
Drp(i,m-1,1){
int now=i+1;
while (a[now].p>a[i].p) now=sml[now];
sml[i]=now;
}
ll Ans=0,gas=n;
Rep(i,1,m+1){
gas-=a[i].x-a[i-1].x;
if (gas<0) return puts("-1"),0;
int Min=min(n,a[sml[i]].x-a[i].x);
if (gas<Min){
Ans+=1ll*(Min-gas)*a[i].p;
gas=Min;
}
}
printf("%I64d\n",Ans);
}
Sep 11, 2022 01:07:59 AM
Since the Government of AP also provided Computer labs for students in all Government schools also.Computer Knowledge is very much essential nowadays. Even Checking the Results of various examinations, AP SSC computer Question Paper Downloading hall tickets and study materials for multiple exams and booking tickets etc ..need minimum Technical Knowledge is much more important for everyone. Since the Government of AP also provided Computer labs for students in all Government schools also.