题意：
给四个数据 n, x, y, d。 n为书总共多少页，x为当前页数，y为目标页数，一次必须翻d页，但是范围在1~n，询问最少翻的次数
情况
1. abs(x-y)%d == 0 正好到达 则输出 abs(x-y)/d
2.往前翻到 1 此时为1 到 y 。 当 (y-1)%d == 0 则说明从1 可以翻到y
3. 往后翻到n 此时为n 到y。 当（n-y) %d == 0 说明可以从n翻到y
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
int main() {
int T, n, x, y, d;
scanf("%d", &T);
while(T--) {
int ans = inf;
scanf("%d%d%d%d", &n,&x,&y,&d);
if(abs(x-y)%d == 0) { printf("%d
", abs(x-y)/d); continue ;}
if((y-1)%d == 0) ans = min(ans, (x-1)/d+1 + (y-1)/d);
if((n-y)%d == 0) ans = min(ans, + (n-x)/d + 1 + (n-y)/d);
if(ans == inf) printf("-1
");
else printf("%d
", ans);
}
}题意：给n的字符的字符串，只有s与g，交换两个字母，让g的连续长度最长。输出最长的值
思路：最长肯定是GGGGSGGGGG这种最长，我们就记录一个S前后的g的长度。前为a后为b则答案为a+b+1
特殊情况就是没有交换的S，我们的S必须交换成G。 如GGSGG 则答案为4不为5 a+b+1 = 2 + 2 + 1
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int MaxN = 1e5 + 5;
char s[MaxN];
int main() {
int n;
scanf("%d%s", &n, s);
int a = 0, b = 0, c = 0, ans = 0;
for(int i = 0; i < n; i++) {
if(s[i] == 'G') a++, c++;
else {
b = a;
a = 0;
}
ans = max(ans, a + b + 1);
}
ans = min(c, ans); //ans最大也不能超过G的数量
printf("%d
", ans);
}前缀和。。有点意思把
const int MaxN = 1e5 + 5;
int ans[MaxN];
vector<int> v[MaxN];
bool cmp(int a, int b) { return a > b; }
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) {
int s, r;
scanf("%d%d", &s, &r);
v[s].push_back(r);
}
int cnt = -1; // 记录v[i].size()的最大值
for(int i = 1; i <= m; i++) {
int len = v[i].size(), sum = 0;
sort(v[i].begin(), v[i].end(), cmp);
cnt = max(cnt, len);
for(int j = 0; j < len; j++) {
sum += v[i][j];
if(sum < 0) break;
ans[j+1] += sum;
}
}
sort(ans + 1, ans + 1 + cnt);
printf("%d
", ans[cnt]);
}
建立一个直径最大的数。度大于1 的建立直径，然后将1添上
一个错误的答案。求一个有缘人
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
int ans[510][510];
struct node{
int val;
int id;
}arr[510];
bool cmp(node a, node b) { return a.val < b.val; }
int main() {
int n, num1 = 0, cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &arr[i].val);
if(arr[i].val == 1) num1++;
arr[i].id = i;
}
sort(arr + 1, arr + n + 1, cmp);
if(num1 == n) { printf("NO
"); return 0; }
for(int i = num1+1; i < n; i++) {
ans[arr[i].id][arr[i+1].id] = 1;
cnt++;
arr[i].val--;
arr[i+1].val--;
}
int p = num1;
for(int i = n; i > num1; i--) {
while(arr[i].val && p) {
cnt++;
ans[arr[p].id][arr[i].id] = 1;
arr[i].val--;
p--;
}
}
if(p) { printf("NO
"); return 0; }
printf("YES %d
", min(n-num1+1, n-1));
printf("%d
", cnt);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(ans[i][j]) printf("%d %d
", i, j);
}
一个a了的答案
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
int ans[510][510];
struct node{
int val;
int id;
}arr[510];
bool cmp(node a, node b) {
return a.val < b.val;
}
int main() {
int n, num1 = 0, cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &arr[i].val);
if(arr[i].val == 1) num1++;
arr[i].id = i;
}
if(num1 == 0) num1 = 1;
sort(arr + 1, arr + n + 1, cmp);
if(num1 == n) {
printf("NO
");
return 0;
}
for(int i = num1; i < n; i++) {
ans[arr[i].id][arr[i+1].id] = 1;
cnt++;
arr[i].val--;
arr[i+1].val--;
}
int p = num1-1;
for(int i = n; i >= num1; i--) {
while(arr[i].val && p) {
cnt++;
ans[arr[p].id][arr[i].id] = 1;
arr[i].val--;
p--;
}
}
if(p) { printf("NO
"); return 0; }
printf("YES %d
", min(n-num1+1, n-1));
printf("%d
", cnt);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(ans[i][j]) printf("%d %d
", i, j);
}