CF1490EAccidentalVictory(前缀和)

题目传送门
这道题我们来寻找性质&＃xff0c;用一个结构体来存储数据的值和数据的位置&＃xff0c;并对数据的值将进行排序&＃xff0c;并求前缀和&＃xff0c;如果i-1的前缀和小于a[i]那么答案就一定不在1~i-1之间了&＃xff0c;答案在i ~ n这个区间&＃xff0c;因此记录下来&＃xff0c;最后的ans以后的所有位置用一个数组存放起来&＃xff0c;再对这个数组排序&＃xff0c;最后的答案就是这个数组的数据。

#include
#include
#include
using namespace std;
typedef long long ll;
struct node{ll num;ll p;
}s[2102100];
ll sum[2102120];
ll an[21020000];
bool cmp(node x,node y){return x.num<y.num;
}
int main(){ll T;cin>>T;while(T--){ll n;cin>>n;for(ll i&＃61;1;i<&＃61;n;i&＃43;&＃43;){cin>>s[i].num;s[i].p&＃61;i;} sort(s&＃43;1,s&＃43;1&＃43;n,cmp);for(ll i&＃61;1;i<&＃61;n;i&＃43;&＃43;){sum[i]&＃61;s[i].num&＃43;sum[i-1];}ll ans&＃61;1;//记录起始位置 for(ll i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(sum[i-1]<s[i].num)ans&＃61;i;if(sum[i-1]&＃61;&＃61;0)ans&＃61;i;}if(sum[n]&＃61;&＃61;0)ans&＃61;n&＃43;1;ll o&＃61;0;for(ll i&＃61;ans;i<&＃61;n;i&＃43;&＃43;)an[&＃43;&＃43;o]&＃61;s[i].p;if(ans<&＃61;n)sort(an&＃43;1,an&＃43;1&＃43;o);printf("%lld\n",o);for(ll i&＃61;1;i<&＃61;o;i&＃43;&＃43;)printf("%lld ",an[i]);printf("\n");}return 0;
}