给出矩形四个顶点的坐标,求出矩形面积;
记录最大的横纵坐标,以及最小的横纵坐标,最大的横坐标减去最小的横坐标就是矩形的一个边长,纵坐标类似减就是矩形的另一个边长
#include<iostream>
#include<algorithm>
using namespace std;
int t;
void solve(){
int x1=-0x3f3f3f3f;
int y1=-0x3f3f3f3f;
int x2=0x3f3f3f3f;
int y2=0x3f3f3f3f;
for(int i=0;i<4;i++)
{
int x,y;
cin>>x>>y;
x1=max(x,x1);
x2=min(x,x2);
y1=max(y,y1);
y2=min(y,y2);
}
cout<<(x1-x2)*(y1-y2)<<endl;
}
int main(){
cin>>t;
while(t--) solve();
return 0;
}
给出两个01串,对其中一个01串操作,可以交换两个我位置的数字,或者翻转某个位置的数字,输出使两串位置对应相等最小的操作次数。
因为要输出最小的操作次数,所以当 a i = 1 a_{i}=1 ai?=1, b i = 0 b_{i}=0 bi?=0且存在 a j = 0 a_{j}=0 aj?=0, b j = 1 b_{j}=1 bj?=1时,最好的操作就是交换,因为可以使得两个位置都可以对应相等,当没有位置可以交换时,才进行翻转操作。若 a i = 1 a_{i}=1 ai?=1, b i = 0 b_{i}=0 bi?=0有x个, a j = 0 a_{j}=0 aj?=0, b j = 1 b_{j}=1 bj?=1情况有x个,则最少的操作次数取决于 m a x ( x , y ) max(x,y) max(x,y)。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10010;
int a[N],b[N];
int t;
void solve(){
int n;
int x=0,y=0;
string a,b;
cin>>n;
cin>>a>>b;
for(int i=0;i<n;i++){
if(a[i]=='1'&&b[i]=='0') x++;
if(a[i]=='0'&&b[i]=='1') y++;
}
cout<<max(x,y)<<endl;
}
int main(){
cin>>t;
while(t--) solve();
return 0;
}
需要在n个时间段( m 1 m_{1} m1?, m 2 m_{2} m2?, m 3 m_{3} m3?… m n m_{n} mn?)发送短信,初始手机电量为 f,待机每分钟消耗a个电,关机再开机这个操作需要消耗b个电,问是否能在电消耗完之前发送n条短信。
贪心的思想求出发送完n条短信所需要的总时间 s u m sum sum,若时间大于等于f则无法完成,否则可以,每次比较关机开机和待机 哪个耗电最少,加到 s u m sum sum上去,最后和 f f f比较,输出结果即可。
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int t;
void solve(){
int n,f,a,b;
int temp=0;
int sum=0;
int m;
cin>>n>>f>>a>>b;
for(int i=1;i<=n;i++){
cin>>m;
sum+=min((m-temp)*a,b);
temp=m;
}
if(sum>=f) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
signed main(){
cin>>t;
while(t--) solve();
return 0;
}
给出两个长度分别是n,m的数组a,b,在b数组中选出n个组成新数组c,使得 ∑ i = 0 n ( ∣ a i ? c i ∣ ) \sum_{i=0}^n(\lvert a_i-c_i\rvert) ∑i=0n?(∣ai??ci?∣)值最大,并输出最大值。
贪心思想对两个数组排序,分别将a数组的最大值和b数组的最小值做差,以及a数组的最小值和b数组的最大值做差,差值大的即为此次配对。
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],b[N];
int t;
void solve(){
int n,m;
int sum=0;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int al=1,ar=n,bl=1,br=m;
for(int i=1;i<=n;i++){
if(abs(a[al]-b[br])>abs(a[ar]-b[bl])){
sum+=abs(a[al]-b[br]);
al++;
br--;
}
else{
sum+=abs(a[ar]-b[bl]);
ar--;
bl++;
}
}
cout<<sum<<endl;
}
signed main(){
cin>>t;
while(t--) solve();
return 0;
}
Alice和Bob玩游戏,给定棋盘为h行,m列,给定Alice和Bob棋子的初始坐标,Alice和Bob轮流移动棋子,Alice先手移动,如果爱丽丝在回合开始时位于坐标为 ( x a , y a ) (x_{a},y_{a}) (xa?,ya?) 的单元格中,那么她可以将筹码移动到 ( x a + 1 , y a ) (x_{a}+1,y_{a}) (xa?+1,ya?) 、$ (x_{a}+1,y_{a}?1) 或 或 或(x_{a}+1,y_{a}+1)$单元格中的一个。鲍勃在轮到他时,可以从坐标为 ( x b , y b ) (x_{b},y_{b}) (xb?,yb?) 的单元格移动 ( x b ? 1 , y b ) (x_{b}?1,y_{b}) (xb??1,yb?) 、 ( x b ? 1 , y b ? 1 ) (x_{b}?1,y_{b}?1) (xb??1,yb??1) 或 ( x b ? 1 , y b + 1 ) (x_{b}?1,y_{b}+1) (xb??1,yb?+1)。双方都想把对方的棋子吃掉,假设两人都是最佳状态下棋,求谁会赢的比赛,若无法将对方吃掉则为平局。
有三种情况
1.当
Δ
\Delta
Δ
x
x
x
<
=
<=
<=
0
0
0时一定会平局,因为Alice移动一次就会下落一层,而Bob移动一次会上升一层,此时初始位置Alice在Bob下面所以就只能平局。
2.当
Δ
\Delta
Δ
x
x
x为奇数时,因为Alice和Bob每次移动
Δ
\Delta
Δ
x
x
x都会减一,所以此时只有Alice可能获胜,这时就变成Alice追Bob,Bob只能想法躲避,若Alice在Bob左上方,Alice会往右下方移动,Bob只会往右上方移动,若两个棋子到达相同层时,Alice无法追上Bob则平局,否则Alice获胜,反之亦然。
3.分析方法与上面类似,换成Bob追Alice。
#include<iostream>
#include<algorithm>
using namespace std;
int t;
void solve(){
int h,w,xa,ya,xb,yb;
cin>>h>>w>>xa>>ya>>xb>>yb;
int dx=xb-xa;
int stepa=(xb-xa+1)/2,stepb=(xb-xa)/2;
if(dx<=0) cout<<"Draw"<<endl;
else if(dx%2){
if(ya<yb){
int run=min(w-yb,stepb);
if(ya+stepa>=yb+run) cout<<"Alice"<<endl;
else cout<<"Draw"<<endl;
}
else{
int run=min(yb-1,stepb);
if(ya-stepa<=yb-run) cout<<"Alice"<<endl;
else cout<<"Draw"<<endl;
}
}
else{
if(ya<yb){
int run=min(ya-1,stepa);
if(yb-stepb<=ya-run) cout<<"Bob"<<endl;
else cout<<"Draw"<<endl;
}
else{
int run=min(w-ya,stepa);
if(yb+stepb>=ya+run) cout<<"Bob"<<endl;
else cout<<"Draw"<<endl;
}
}
}
int main(){
cin>>t;
while(t--) solve();
return 0;
}